Longest Substring with K Distinct Characters

JS|Sliding Window Technique

Please subscribe my youtube channel: FrontEnd Interview Preparation: https://www.youtube.com/channel/UC-elmWUfbcbmvuhlS12nCtg

The best thing I came across was the problem-solving patterns like Sliding Window. Following this pattern helped me nurture my ability to map a new problem to an already known problem.

Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.
Input: String="araaci", K=2
Output: 4
Explanation: The longest substring with no more than '2' distinct characters is "araa".

Let’s use here sliding window approach with two set pointers start_window and currentWindowlength serving as the window boundaries. This algorithmic technique is used when we need to handle the input data in a specific window size.

Algorithm:

• Set two both pointers at the beginning of the string start_window = 0 and currentWindowlength = 0 and init max substring length max_len = 0.
• While the dict object keys are less than K distinct characters, add the current character in the dict object
• If dict object contains k+1 distinct characters, remove the leftmost character from dict and move the start_window to right. so that the sliding window contains again k distinct characters only.
• update maxLength
• Return 0 if the string is empty or k is equal to zero.

var lengthOfLongestSubstringKDistinct = function(s, k) {
    let dict = {};
    let currentWindowlength = 0;
    let start_window = 0, maxLength = 1;
    for (let i = 0; i < s.length; i++) {
       let char = s[i];
       dict[char] = i;
      if (Object.keys(dict).length > k) {
         start_window = Math.min.apply(null, Object.values(dict));
         delete dict[s[start_window]];
         start_window++;
       }
      currentWindowlength = i - start_window + 1;
      maxLength = Math.max(currentWindowlength, maxLength);
    }
    return maxLength;
};
lengthOfLongestSubstringKDistinct("eceba", 2)

Complexity Analysis

• Time complexity: O(N)
• Space complexity: O(k) since additional space is used only for an ordered dictionary with at most k + 1 elements.

If you want to learn more on data structure, book a session with me on www.startlearncoding.com

• Follow me for more coding interviews.
• This problem is very popular in coding interviews.
• Keep learning, keep growing!
• Don’t forget to follow me for more such articles, and subscribe to our newsletter.
• Let’s connect on LinkedIn!. Please read more for more data structure javascript questions.

Don’t forget to follow The Lean Programmer Publication for more such articles, and subscribe to our newsletter tinyletter.com/TheLeanProgrammer