Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Longest Substring with K Distinct Characters
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a string, find the length of the longest substring in it with no more than K distinct characters.

You can assume that K is less than or equal to the length of the given string.

Example 1:

Input: str="araaci", K=2  
Output: 4  
Explanation: The longest substring with no more than '2' distinct characters is "araa".

Example 2:

Input: str="araaci", K=1  
Output: 2  
Explanation: The longest substring with no more than '1' distinct characters is "aa".

Example 3:

Input: str="cbbebi", K=3  
Output: 5  
Explanation: The longest substrings with no more than '3' distinct characters are "cbbeb" & "bbebi".

Constraints:

  • 1 <= str.length <= 5 * 10<sup>4</sup>
  • 0 <= K <= 50

Solution

To solve this problem, we can use a sliding window approach. The idea is to maintain a window that contains at most ( K ) distinct characters. We will expand the window by including one character at a time from the right, and once the window contains more than ( K ) distinct characters, we will shrink it from the left until it again contains ( K ) or fewer distinct characters.

This approach is effective because it allows us to process the string in linear time, which is efficient for large inputs. By keeping track of the frequency of characters within the window using a hash map, we can efficiently manage the characters and ensure that the window always contains at most ( K ) distinct characters.

Step-by-Step Algorithm

  1. Initialize two pointers, windowStart and windowEnd, both set to 0.
  2. Create a hash map to keep track of the frequency of characters within the current window.
  3. Start a loop with windowEnd ranging from 0 to the length of the string:
    • Add the character at windowEnd to the hash map and update its frequency.
    • If the hash map contains more than ( K ) distinct characters:
      • Remove characters from the left (i.e., move windowStart to the right) until the hash map contains at most ( K ) distinct characters.
      • Decrease the frequency of the leftmost character and remove it from the hash map if its frequency becomes zero.
    • Update the maximum length of the substring found so far.
  4. Return the maximum length.

Algorithm Walkthrough

Let's use the input str = "araaci", K = 2 for a step-by-step walkthrough.

  1. windowStart = 0, windowEnd = 0

    • Add 'a' to the hash map: {'a': 1}
    • Maximum length = 1

  2. windowEnd = 1

    • Add 'r' to the hash map: {'a': 1, 'r': 1}
    • Maximum length = 2

  3. windowEnd = 2

    • Add 'a' to the hash map: {'a': 2, 'r': 1}
    • Maximum length = 3

  4. windowEnd = 3

    • Add 'a' to the hash map: {'a': 3, 'r': 1}
    • Maximum length = max(maxLength, windowEnd - windowStart + 1) = max(0, 3 - 0 + 1) = 4

  5. windowEnd = 4

    • Add 'c' to the hash map: {'a': 3, 'r': 1, 'c': 1}
    • More than ( K ) distinct characters, shrink window from the left:
      • Remove 1 'a': {'a': 2, 'r': 1, 'c': 1}
      • windowStart = 1
      • Remove 1 'r': {'a': 2, 'c': 1}
      • windowStart = 2
    • Maximum length = max(maxLength, windowEnd - windowStart + 1) = max(4, 4 - 2 + 1) = 4

  6. windowEnd = 5

    • Add 'i' to the hash map: {'a': 2, 'c': 1, 'i': 1}
    • More than ( K ) distinct characters, shrink window from the left:
      • Remove 'a': {'a': 1, 'c': 1, 'i': 1}
      • windowStart = 3
      • Remove 'a': {'c': 1, 'i': 1}
      • windowStart = 4
    • Maximum length = max(maxLength, windowEnd - windowStart + 1) = max(4, 5 - 4 + 1) = 4
Image

Code

Here is what our algorithm will look like:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Single pass: The algorithm makes a single pass through the string using a sliding window approach. The outer loop iterates over each character in the string, so it runs O(N) times, where N is the length of the input string.

  • Sliding window adjustment: The inner loop adjusts the window size whenever the number of distinct characters exceeds k. The charFrequencyMap keeps track of the frequency of each character in the current window, and both adding and removing characters from the map take constant time on average (O(1)) because hash map operations are typically O(1).

  • Therefore, the overall time complexity is O(N) because the outer loop processes each character once, and the inner loop performs constant-time operations to adjust the window.

Overall time complexity: O(N).

Space Complexity

  • HashMap space: The charFrequencyMap stores up to k + 1 distinct characters in the worst case. Since there can be at most k distinct characters in the map at any given time, the space used by the hash map is O(k).

  • Additional variables: The algorithm uses a few additional variables (windowStart, windowEnd, maxLength), which require constant space, O(1).

Overall space complexity: O(k), where k is the maximum number of distinct characters allowed.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible