具有最大不重复字符的字符串

huangapple go评论97阅读模式
英文:

A string with maximum unrepeated characters

问题

以下是您要翻译的内容:

"Here so far looks great I think. The only issue I am having is erasing the elements from the set and incrementing the left pointer. I am getting some wrong output whereas some right. Need some help with the logic. It is a typical leet code question 3 in which it is asked to print the maximum number of unrepeated string characters. The issue I am facing is in the loop

if (iter != stringSet.end()) {
while (*stringSet.begin() != c) {
stringSet.erase(stringSet.begin());
left++;
}
}

I tried "abcabcbb" and out put I should get is 3, but i got 4.

class Solution {
public:
int lengthOfLongestSubstring(string s) {
int left = 0;
int right = 0;
int maxlength = 0;
set stringSet;

for (;right < s.length(); right++) {
char c = s[right];

auto iter = stringSet.find(c);

if (iter != stringSet.end()) {
while (*stringSet.begin() != c) {
stringSet.erase(stringSet.begin());
left++;
}

} else {
stringSet.insert(c);
maxlength = max(maxlength, right-left+1);
}
}

return maxlength;
}
};"

英文:

Here so far looks great I think. The only issue I am having is erasing the elements from the set and incrementing the left pointer. I am getting some wrong output whereas some right. Need some help with the logic. It is a typical leet code question 3 in which it is asked to print the maximum number of unrepeated string characters. The issue I am facing is in the loop

 if (iter != stringSet.end()) {
            while (*stringSet.begin() != c) {
                stringSet.erase(stringSet.begin());
                left++;
            }

I tried "abcabcbb" and out put I should get is 3, but i got 4.

class Solution {
    public:
    int lengthOfLongestSubstring(string s) {
        int left = 0;
        int right = 0;
        int maxlength = 0;
        set&lt;char&gt; stringSet;
        
        for (;right &lt; s.length(); right++) {
            char c = s[right];
            
            auto iter = stringSet.find(c); 
            
            if (iter != stringSet.end()) {
                while (*stringSet.begin() != c) {
                    stringSet.erase(stringSet.begin());
                    left++;
                }
             
              
            } else {
                stringSet.insert(c);
                maxlength = max(maxlength, right-left+1);
            }
        }
        
        return maxlength;
    }
};

答案1

得分: 1

问题在于当你找到重复的字符时,你只是从集合的开头开始擦除元素,直到重复的字符被移除为止。然而,这种方法是不正确的,因为集合中可能还存在其他仍然存在于当前子字符串中的字符。

要解决这个问题,你需要从集合中擦除元素,直到重复的字符被移除,并且还要调整左指针以移到移除重复字符后的位置。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0;
        int right = 0;
        int maxlength = 0;
        set<char> stringSet;
        
        while (right < s.length()) {
            char c = s[right];
            
            auto iter = stringSet.find(c); 
            
            if (iter != stringSet.end()) {
                while (*stringSet.begin() != c) {
                    stringSet.erase(s[left]); // 使用字符值而不是迭代器从集合中擦除元素
                    left++;
                }
                
                stringSet.erase(s[left]); // 擦除重复的字符本身
                left++; // 将左指针移动到移除重复字符后的位置
            } else {
                stringSet.insert(c);
                maxlength = max(maxlength, right - left + 1);
                right++;
            }
        }
        
        return maxlength;
    }
};
英文:

The issue is that when you find a repeated character, you are only erasing elements from the beginning of the set until the repeated character is removed. However, this approach is incorrect because there could be other characters in the set that are still present in the current substring.

To fix this, you need to erase elements from the set until the repeated character is removed and also adjust the left pointer to move to the position after the removed repeated character.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0;
        int right = 0;
        int maxlength = 0;
        set&lt;char&gt; stringSet;
        
        while (right &lt; s.length()) {
            char c = s[right];
            
            auto iter = stringSet.find(c); 
            
            if (iter != stringSet.end()) {
                while (*stringSet.begin() != c) {
                    stringSet.erase(s[left]); // Erase elements from the set using the character value, not the iterator
                    left++;
                }
                
                stringSet.erase(s[left]); // Erase the repeated character itself
                left++; // Move the left pointer to the position after the removed repeated character
            } else {
                stringSet.insert(c);
                maxlength = max(maxlength, right - left + 1);
                right++;
            }
        }
        
        return maxlength;
    }
};

huangapple
  • 本文由 发表于 2023年8月4日 01:59:21
  • 转载请务必保留本文链接:https://go.coder-hub.com/76830561.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定