12. Longest Substring with At Most K Distinct Characters

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

Example 1:

Input: S = "eceba" and k = 3
Output: 4
Explanation: T = "eceb"

Example 2:

Input: S = "WORLD" and k = 4
Output: 4
Explanation: T = "WORL" or "ORLD"

Solution: (Sliding Window)

class Solution
{
public:
    int lengthOfLongestSubstringKDistinct(string &s, int k)
    {
        // write your code here
        if(k == 0){
            return 0;
        }

        unordered_map<char, int> m;
        int res = 0;
        int start = 0;
        int charCount = 0;

        for (int i = 0; i < s.length(); i++)
        {

            if (!m[s[i]])
            {
                charCount++;
            }

            m[s[i]]++;

            while (charCount > k)
            {

                m[s[start]]--;
                if (m[s[start]] == 0)
                {
                    charCount--;
                }
                start++;
            }

            
             res = max(res, (i - start)+1);
            
        }

        return res;
    }
};

Time Complexity: O(n)