Sliding Window Technique - Part 8

Another approach to use sliding window technique is the following:

1/ Still have right and left pointers

2/ First loop is controlled by the right one, meaning it runs thru all the way to the length of the string

3/ The second loop is controlled by the left pointer (left over)

In all it is still O(2n). The problem below keeps track of K distinct chars in the sliding window. Code is down below, cheers, ACC

Longest Substring with At Most K Distinct Characters - LeetCode

340. Longest Substring with At Most K Distinct Characters

Medium

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

 

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: The substring is "aa" with length 2.

 

Constraints:

• 1 <= s.length <= 5 * 104
• 0 <= k <= 50

Accepted

317,919

Submissions

659,182

public int LengthOfLongestSubstringKDistinct(string s, int k)
{
    if (k == 0) return 0;

    Hashtable slidingWindow = new Hashtable();

    int left = 0;
    int right = 0;
    int retVal = 0;
    while (right < s.Length)
    {
        if (slidingWindow.Count < k || (slidingWindow.Count == k && slidingWindow.ContainsKey(s[right])))
        {
            if (!slidingWindow.ContainsKey(s[right])) slidingWindow.Add(s[right], 0);
            slidingWindow[s[right]] = (int)slidingWindow[s[right]] + 1;
            retVal = Math.Max(retVal, right - left + 1);
            right++;
        }
        else
        {
            if (slidingWindow.ContainsKey(s[left]))
            {
                slidingWindow[s[left]] = (int)slidingWindow[s[left]] - 1;
                if ((int)slidingWindow[s[left]] == 0) slidingWindow.Remove(s[left]);
                left++;
            }
        }
    }

    while (left < s.Length)
    {
        if (slidingWindow.ContainsKey(s[left]))
        {
            slidingWindow[s[left]] = (int)slidingWindow[s[left]] - 1;
            if ((int)slidingWindow[s[left]] == 0) slidingWindow.Remove(s[left]);
            if (slidingWindow.Count <= k) retVal = Math.Max(retVal, s.Length - left);
        }
        left++;
    }

    return retVal;
}