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.

S: hash map,窗口型two pointer

每一次发现重复，需要从前面重复字符index+1开始算substring。要存储substring中每一个出现过的字符和对应的index，考虑用hashmap。因为string的每一个元素是8byte，最多只有$$2^8$$ = 256种可能，可以用数组代替hashmap。因为要排除掉数组中已经不在当前substring里的元素，需要存储substring的起始index,当数组中元素index>起始index时才是在当前substring中的。

    int lengthOfLongestSubstring(string s) {
        vector<int> idx(256, -1); //hashmap
        int len = 0, n = s.size();
        for (int i = 0, j = 0; i < n && j < n;) {
            while (j < n && (idx[s[j]] < i)) {
                idx[s[j]] = j;
                j++;
            }
            len = max(len, j - i);
            i = idx[s[j]] + 1;
        } 
        return len;
    }

159. Longest Substring with At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

S1：hashmap + sliding window

存储两个不同元素出现的次数，当出现新的元素时，遍历substring减去count直到count=1，抹去该元素。此方法可以扩展到n distinct characters。

    int lengthOfLongestSubstringTwoDistinct(string s) {
        int size = s.size(), start = 0, maxLength = 0;
        unordered_map<char, int> count;
        for(int i = 0; i < size; ++i){
            count[s[i]]++;
            while(count.size() > 2){
                if(--count[s[start]] == 0) count.erase(s[start]); 
                start++;
            }
            maxLength = max(maxLength, i - start + 1);
        }
        return maxLength;
    }

S2：sliding window

维护一个sliding window，以及这个window里的两个字母c1, c2以及它们的最后一次出现的位置p1, p2。当出现一个新字母时，把sliding window的头移到p1, p2中较前面那个的后一位。

    int lengthOfLongestSubstringTwoDistinct(string s) {
        char c1 , c2;
        int idx1 = -1, idx2 = -1;
        int curLen = 0, maxLen = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (idx2 == -1 || s[i] == c2) {
                c2 = s[i];
                idx2 = i;
                curLen++;
            } else if (idx1 == -1 || s[i] == c1) {
                c1 = s[i];
                idx1 = i;
                curLen++;
            } else {
                curLen = i - idx1;
                idx1 = idx2;
                c1 = c2;
                c2 = s[i];
                idx2 = i;
            }
            if (idx1 > idx2) {
                swap(c1, c2);
                swap(idx1, idx2);
            }
            maxLen = max(maxLen, curLen);
        }
        return maxLen;
    }

340. Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “eceba” and k = 2,

T is "ece" which its length is 3.

Show Company Tags
Show Tags
Show Similar Problems

S：hashmap + sliding window

    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int size = s.size(), start = 0, maxLength = 0;
        unordered_map<char, int> count;
        for(int i = 0; i < size; ++i){
            count[s[i]]++;
            while(count.size() > k){
                if(--count[s[start]] == 0) count.erase(s[start]); 
                start++;
            }
            maxLength = max(maxLength, i - start + 1);
        }
        return maxLength;

    }

//two pinter 模板
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        vector<int> count(256, 0);
        int n = s.size();
        int len = 0;
        for (int i = 0, j = 0; i < n && j < n; ++i){
            while(j < n && k >= 0) {
                if (count[s[j]] == 0) {
                    k--;
                }
                count[s[j]]++;
                j++;
            }
            int curLen = j - i;
            if (k < 0) curLen--;  // k < 0时j多++了一次
            len = max(len, curLen);

            count[s[i]]--;
            if (count[s[i]] == 0) {
                k++;
            }
        }
        return len;     
    }

424. Longest Repeating Character Replacement

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and k will not exceed 104.

Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.
Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
Show Company Tags
Hide Similar Problems

S:sliding window

sliding window问题关键是如何维护window。这一题关键是存储当前window中出现次数最多的次数max_count, max_count+k即为当前可以得到的最大subarray的长度

    int characterReplacement(string s, int k) {
        vector<int> count(26, 0);
        int start = 0, max_count = 0;
        for(int i = 0; i < s.size(); ++i){
            count[s[i]-'A']++;
            max_count = max(max_count, count[s[i]-'A']);
            if(max_count + k < i - start + 1){//s[i]不是max_count对应的字符，i增加了而max_count没有
                count[s[start]-'A']--;
                start++;//start前移一步
            }
            //other case：
            //1. max_count + k > i - start + 1时，k个可替换名额没有用完，直接前进
            //2. max_count + k == i - start + 1时， s[i]就是max_count对应的字符，
            //   此时i和max_count同时加一，直接前进
        }
        return s.size() - start;
    }