leetcode 3. longest substring without repeating characters

Description：

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

Solution:

维护两个指针，遍历整个字符串，找到了一个包含重复的子串（利用hash table判断），就用第二个指针去尝试缩小区间，找到一个没有重复的子串，并在过程中记录下最长的子串即可。

class  
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        if (s.empty())
		return 0;

        int start = 0, end = 0, max_len = INT_MIN, counter = 0;
        vector<int> table(256, 0);

        while (end < s.size())
        {
            
            if (table[s[end]] > 0)
                ++counter;

            ++table[s[end]];
            ++end;
            
            while (counter > 0)
            {
                // if s[start] occur more than once.
                if (table[s[start]] > 1)
                    --counter;

                --table[s[start]];
                ++start;

            }
            // update the max length.
            max_len = max(max_len, end - start);
        }
        return max_len;
    }
};

leetcode 3. longest substring without repeating characters

近期文章

近期评论

标签

热门

文章归档

分类目录

功能