How to Solve Longest Substring with At Most K Distinct Characters
Longest Substring with At Most K Distinct Characters Introduction
Longest Substring with At Most K Distinct Characters Introduction
The Longest Substring with At Most K Distinct Characters problem asks us to find the length of the longest substring in it with no more than K distinct characters of a given string. This problem can be tackled using a sliding window and requires careful consideration and checks for the frequency of characters and the maximum length of our window as we go through the string.
Longest Substring with At Most K Distinct Characters Problem
Longest Substring with At Most K Distinct Characters Problem
Given a string, find the length of the longest substring in it with no more than K distinct characters.
Example Input and Output
Input: s = "abcdeffg", k = 3
Output: Length of the longest substring with at most 3 distinct characters: 4
Longest Substring with At Most K Distinct Characters Solutions
Longest Substring with At Most K Distinct Characters Solutions
To solve this problem, we can use a sliding window approach along with a hash table to keep track of the frequency of characters in the current window. We can start by initializing two pointers, left and right, both pointing to the beginning of the string. As we iterate through the string, we expand the window by moving the right pointer to the right. At each step of the way, we update the frequency of the current character in the hash table.
If the number of distinct characters in the window is greater than K, we can shrink the window by moving the left pointer to the right until we have at most K distinct characters in the window again. While doing this, we keep track of the maximum length of the window encountered so far. By repeatedly expanding and shrinking the window, we can go through the entire string to find the length.
Note:
The JavaScript solution uses an object (charFrequency) as a substitute for a hash map to store the character frequencies.
def longest_substring_k_distinct(s, k):
window_start = 0
max_length = 0
char_frequency = {}
for window_end in range(len(s)):
right_char = s[window_end]
char_frequency[right_char] = char_frequency.get(right_char, 0) + 1
while len(char_frequency) > k:
left_char = s[window_start]
char_frequency[left_char] -= 1
if char_frequency[left_char] == 0:
del char_frequency[left_char]
window_start += 1
max_length = max(max_length, window_end - window_start + 1)
return max_length
s = "abcdeffg"
k = 3
length = longest_substring_k_distinct(s, k)
print("Length of the longest substring with at most", k, "distinct characters:", length)1def longest_substring_k_distinct(s, k):
2 window_start = 0
3 max_length = 0
4 char_frequency = {}
5
6 for window_end in range(len(s)):
7 right_char = s[window_end]
8 char_frequency[right_char] = char_frequency.get(right_char, 0) + 1
9
10 while len(char_frequency) > k:
11 left_char = s[window_start]
12 char_frequency[left_char] -= 1
13 if char_frequency[left_char] == 0:
14 del char_frequency[left_char]
15 window_start += 1
16
17 max_length = max(max_length, window_end - window_start + 1)
18
19 return max_length
20
21s = "abcdeffg"
22k = 3
23
24length = longest_substring_k_distinct(s, k)
25print("Length of the longest substring with at most", k, "distinct characters:", length)Time/Space Complexity Analysis
- Time Complexity: O(N), where N is the length of the input string. We iterate through the string once, maintaining a sliding window of characters and updating the hash table in constant time.
- Space Complexity: O(K), where K is the maximum number of distinct characters allowed. The hash table will store at most K distinct characters along with their frequencies.
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
