340. Longest Substring with At Most K Distinct Characters

https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/

1. Use Sliding Window & Hashmap:

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int n = s.length();
        if(n == 0 || k == 0){
            return 0;
        }
        int l = 0, r = 0;
        map<char, int> rightmost_pos;
        int max_len = 1;
        while(r < n) {
            rightmost_pos[s[r]] = r;
            if(rightmost_pos.size() > k){ //has k + 1 distinct numbers
                int lowest_index = INT_MAX;
                for(pair<char, int> element : rightmost_pos) {
                    lowest_index = min(lowest_index, element.second); //find the leftmost index in map
                }
                rightmost_pos.erase(s[lowest_index]); //erase the left most one
                l = lowest_index + 1;
            }
            max_len = max(max_len, r - l + 1);
            r++;
        }
        return max_len;
    }
};

Time Complexity: O(N)
Space Complexity: O(k)