Two pointers short C++ solution using map


  • 1

    Two pointers i, j to record the sliding window. In the map, the key is char c, and the value is the index of the last appeared c till j. When there is less than or equal to k characters in the map, we advance j, and update the map with the index as well as update the longest length. When we have more than k distinct characters in the map, we advance i one step at a time, when m[s[i]] = i, we know it's the last s[i] we have visited so far, so we can erase s[i], and the distinct characters is now decreased by 1, that we can continue advancing j now until the next time we hit the k limit or j reaches the end.

    class Solution {
    public:
        int lengthOfLongestSubstringKDistinct(string s, int k) {
            int ans = 0, i = 0, j = 0;
            unordered_map<char, int> m;
    
            while(i <= j){
                while(j < s.size() && m.size() <= k){
                    m[s[j]] = j;
                    if(m.size() <= k) ans = max(ans, j - i + 1);
                    j++;
                }
                
                if(m[s[i]] == i) m.erase(s[i]);
                i++;
            }
            
            return ans;
        }
    };

  • 0

    @Ximin.Z
    Do we not need

    while ( i <= j < n) {
    

    to make sure i < s.size() ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.