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 {
        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);
                if(m[s[i]] == i) m.erase(s[i]);
            return ans;

  • 0

    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.