3. Longest Substring Without Repeating Characters

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.

解法

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        // 用一個hash table來紀錄有重複字元出現在array的第幾個element
        unordered_map<char, int> charmap;
        // 最大的不重複字元substring長度跟每次要去定位每一個substring的endflag
        int maxlength = 0, flag = -1;
        
        for (int i = 0; i < s.size(); i++)
        {
            // 一開始發現s[i]不出現
            if (charmap.count(s[i]) > 0)
            {
                //比大小更新end
                flag = max(charmap[s[i]], flag);
            }
            
            //標記它已經出現過了
            charmap[s[i]] = i;
            
            //更新目前為止最大的不重複字元substring長度
            maxlength = max(maxlength,(i - flag));
        }
        
        return maxlength;
        
    }
};