Longest Substring with At Most K Distinct Characters LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon AppDynamics Facebook Google LinkedIn Microsoft Oracle Snapchat Twitter Uber WishViews 3601

Problem Statement

Longest Substring with At Most K Distinct Characters LeetCode Solution – 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:

Test Case 1:

Input:

S = “bacc”

K = 2

Output:

3

Test Case 2:

Input:

S = “ab”

K = 1

Output:

1

Explanation for Longest Substring with At Most K Distinct Characters LeetCode Solution:

i) For the first test case, “acc” is the longest substring with at most  2 unique characters.

ii) For the second test case, either “a” or “b” are the longest substring with at most 1 unique character.

Approach

Idea:

First, we need to identify the problem is of which type. Here we need to find a substring based on some conditions.  For some windows/ substrings in the string, we need to check the condition to get the correct result. So we can know that this question is related to the Sliding window technique. Here we need to find out the size of the window for which the condition is true.

  1. So we can iterate over the window to check if the condition is true but for that, we need to keep track of the count of every character in that window/substring. We can do that using a map or we can use an array where we will use the character as indices of the array to keep track of the count.
  2. Once the no of unique characters is more than K, we will keep removing the characters from the front until the no of unique characters = K.
  3. When no of unique characters = K, we can find the length of the substring and keep track of the maximum length.

Code

Java Program for Longest Substring with At Most K Distinct Characters LeetCode Solution

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String S, int K) {
        int[] charCount = new int[256];
        char[] chS = S.toCharArray();
        int distinctNum = 0, leftIndex = 0, maxLen = 0;
        for (int rightIndex = 0; rightIndex < chS.length; rightIndex++) {
            if (charCount[chS[rightIndex]]++ == 0) distinctNum++;
            if (distinctNum > K) {
                while (--charCount[chS[leftIndex++]] > 0);
                distinctNum--;
            }
            maxLen = Math.max(maxLen, rightIndex - leftIndex + 1);
        }
        return maxLen;
    }
}

C++ Program for Longest Substring with At Most K Distinct Characters LeetCode Solution

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string S, int K) {
      int charCount[256] = {}; 
      int distinctNum = 0, leftIndex = 0, maxLen = 0;
      for (int rightIndex = 0; rightIndex < S.size(); rightIndex++) { 
        if (charCount[S[rightIndex]]++ == 0) 
          distinctNum++; 
        if (distinctNum > K) { 
          while (--charCount[S[leftIndex++]] > 0); 
          distinctNum--; 
        } 
        maxLen = max(maxLen, rightIndex - leftIndex + 1); 
      } 
      return maxLen;
    }
};

Complexity Analysis for Longest Substring with At Most K Distinct Characters LeetCode Solution

Time Complexity

Here we will feel, we are iterating over an array that will take O(n) time, and the inner while loop will take O(K) time. (n is the length of the string). But If we closely look into the inner while loop using an example, we will notice we traverse each and every character of string at most 2 times. So time complexity comes out as O(2*n) => O(n)

Space Complexity

Here we are using an array to store the frequency count. But it is always a fixed size. So basically space complexity is O(256) => O(1). We can also use a map instead of an array, there at max, we will store K  elements. So the space complexity will be O(K). (K is the number of unique characters)

Reference: https://en.wikipedia.org/wiki/Substring

Translate »