Longest Substring With At Most K Distinct Characters
Sliding Window / 2 Pointer
Longest and Smallest Window Problems
Hard
- Fun Fact: The core concept of this problem is used in text and data analysis software
- For example, in social media applications, analyzing the length of the longest substring with at most k distinct characters could help detect, track, or summarize major trends/topic, spam posts or even potential security breaches
- Similarly, in bioinformatics, this idea could be applicable in DNA sequencing, where the longest substring of a DNA fragment with distinct kinds of nucleotides is important
Given a string s and an integer k.Find the length of the longest substring with at most k distinct characters.
Examples:
Input : s = "aababbcaacc" , k = 2
Output : 6
Explanation : The longest substring with at most two distinct characters is "aababb".
The length of the string 6.
Input : s = "abcddefg" , k = 3
Output : 4
Explanation : The longest substring with at most three distinct characters is "bcdd".
The length of the string 4.
Input : s = "abccab" , k = 4
Constraints
- 1 <= s.length <= 105
- 1 <= k <= 26
Hints
- Use a sliding window approach to find the longest substring with at most k distinct characters.
- "Use a hash map to store the frequency of each character in the current window. Keep track of the maximum length encountered during the traversal. "
Company Tags
Cloudflare
Bungie
Nutanix
Roche
Ernst & Young
AMD
Boston Consulting Group
Riot Games
Morgan Stanley
Etsy
Red Hat
Visa
Uber
IBM
Oracle
Johnson & Johnson
Micron Technology
JPMorgan Chase
GE Healthcare
Salesforce
Chewy
MongoDB
Alibaba
Goldman Sachs
Reddit
Google
Microsoft
Amazon
Meta
Apple
Netflix
Adobe
Editorial
Intuition:
The idea here is to generate all possible substrings of the given array using two loops and while doing so, check if the number of distinct characters in the current substring is within the allowed limit, using a map data structure. If the number of distinct characters exceed limit, then no need to consider that substring, else calculate the length of the current substring and update the maximum length of substring.
Approach:
maxLen as 0, which will store the maximum length of substrings with at most k distinct characters, mpp an unordered_map to track the count of each character in the current substring.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to find the maximum length of
substring with at most k distinct characters */
int kDistinctChar(string& s, int k) {
/* Variable to store the
maximum length of substring*/
int maxLen = 0;
/* Map to track the count of each
character in the current window*/
unordered_map<char, int> mpp;
/* Iterate through each starting
point of the substring*/
for(int i = 0; i < s.size(); i++){
// Clear map for a new starting point
mpp.clear();
for(int j = i; j < s.size(); j++){
// Add the current character to the map
mpp[s[j]]++;
/* Check if the number of distinct
characters is within the limit*/
if(mpp.size() <= k){
/* Calculate the length of
the current valid substring*/
maxLen = max(maxLen, j - i + 1);
}
else break;
}
}
// Return the maximum length found
return maxLen;
}
};
int main() {
string s = "aaabbccd";
int k = 2;
// Create an instance of Solution class
Solution sol;
int length = sol.kDistinctChar(s, k);
// Print the result
cout << "Maximum length of substring with at most " << k << " distinct characters: " << length << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
import java.util.*;
class Solution {
/* Function to find the maximum length of
substring with at most k distinct characters */
public int kDistinctChar(String s, int k) {
/* Variable to store the
maximum length of substring*/
int maxLen = 0;
/* Map to track the count of each
character in the current window*/
HashMap<Character, Integer> mpp = new HashMap<>();
/* Iterate through each starting
point of the substring*/
for(int i = 0; i < s.length(); i++){
// Clear map for a new starting point
mpp.clear();
for(int j = i; j < s.length(); j++){
// Add the current character to the map
char c = s.charAt(j);
mpp.put(c, mpp.getOrDefault(c, 0) + 1);
/* Check if the number of distinct
characters is within the limit*/
if(mpp.size() <= k){
/* Calculate the length of
the current valid substring*/
maxLen = Math.max(maxLen, j - i + 1);
}
else break;
}
}
// Return the maximum length found
return maxLen;
}
public static void main(String[] args) {
String s = "aaabbccd";
int k = 2;
// Create an instance of Solution class
Solution sol = new Solution();
int length = sol.kDistinctChar(s, k);
// Print the result
System.out.println("Maximum length of substring with at most " + k + " distinct characters: " + length);
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
class Solution:
""" Function to find the maximum length of
substring with at most k distinct characters """
def kDistinctChar(self, s: str, k: int) -> int:
""" Variable to store the
maximum length of substring"""
maxLen = 0
""" Dictionary to track the count of each
character in the current window"""
mpp = {}
""" Iterate through each starting
point of the substring"""
for i in range(len(s)):
# Clear dictionary for a new starting point
mpp.clear()
for j in range(i, len(s)):
# Add the current character to the dictionary
if s[j] in mpp:
mpp[s[j]] += 1
else:
mpp[s[j]] = 1
""" Check if the number of distinct
characters is within the limit"""
if len(mpp) <= k:
""" Calculate the length of
the current valid substring"""
maxLen = max(maxLen, j - i + 1)
else:
break
# Return the maximum length found
return maxLen
if __name__ == "__main__":
s = "aaabbccd"
k = 2
# Create an instance of Solution class
sol = Solution()
length = sol.kDistinctChar(s, k)
# Print the result
print(f"Maximum length of substring with at most {k} distinct characters: {length}")
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
class Solution {
/* Function to find the maximum length of
substring with at most k distinct characters */
kDistinctChar(s, k) {
/* Variable to store the
maximum length of substring*/
let maxLen = 0;
/* Map to track the count of each
character in the current window*/
let mpp = new Map();
/* Iterate through each starting
point of the substring*/
for(let i = 0; i < s.length; i++){
// Clear map for a new starting point
mpp.clear();
for(let j = i; j < s.length; j++){
// Add the current character to the map
let c = s.charAt(j);
mpp.set(c, (mpp.get(c) || 0) + 1);
/* Check if the number of distinct
characters is within the limit*/
if(mpp.size <= k){
/* Calculate the length of
the current valid substring*/
maxLen = Math.max(maxLen, j - i + 1);
}
else break;
}
}
// Return the maximum length found
return maxLen;
}
}
let s = "aaabbccd";
let k = 2;
//Create an instance of Solution class
let sol = new Solution();
let len = sol.kDistinctChar(s, k);
//Print the output
console.log(`Maximum length of substring with at most ${k} distinct characters: ${len}`);
Complexity Analysis:
Time Complexity:O(N2), where N is the size of the array. As for every element of the array the inner loop runs for N times.Space Complexity: O(k), as at most the map data structure is holding k elements.
Intuition:
Here, the idea is to use sliding window approach with hashMap to solve this problem in optimal way. Which ensures that to find the longest substring with at most k distinct characters efficiently by maintaining a sliding window and using a hashmap to keep track of character frequencies within the window.
Approach:
l and r pointers to 0 which represent the left and right boundaries of the current window respectively, maxLen initialized to 0 to store the maximum length of substring with at most k distinct characters found so far, mpp a hashMap is used to track the frequency of characters within the current window.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to find the length of the longest
substring with at most k distinct characters*/
int kDistinctChar(string& s, int k) {
/* Initialize left pointer, right pointer,
and maximum length of substring*/
int l = 0, r = 0, maxLen = 0;
// Hash map to store character frequencies
unordered_map<char, int> mpp;
while (r < s.size()) {
// Increment frequency of current character
mpp[s[r]]++;
/* If the number of distinct characters
exceeds k, shrink the window from the left*/
while (mpp.size() > k) {
// Decrement frequency of character at left pointer
mpp[s[l]]--;
if (mpp[s[l]] == 0) {
/* Remove character from map
if its frequency becomes zero*/
mpp.erase(s[l]);
}
// Move left pointer to the right
l++;
}
/* Update maximum length of substring with
at most k distinct characters found so far*/
if (mpp.size() <= k) {
maxLen = max(maxLen, r - l + 1);
}
// Move right pointer
r++;
}
// Return the maximum length found
return maxLen;
}
};
int main() {
string s = "aaabbccd";
// Create an instance of the Solution class
Solution sol;
int res = sol.kDistinctChar(s, 2);
// Output the result
cout << "The maximum length of substring with at most " << 2 << " distinct characters is: " << res << endl;
return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
import java.util.*;
class Solution {
/* Function to find the length of the longest
substring with at most k distinct characters */
public int kDistinctChar(String s, int k) {
/* Initialize left pointer, right pointer,
and maximum length of substring*/
int l = 0, r = 0, maxLen = 0;
// Hash map to store character frequencies
HashMap<Character, Integer> mpp = new HashMap<>();
while (r < s.length()) {
// Increment frequency of current character
char currentChar = s.charAt(r);
mpp.put(currentChar, mpp.getOrDefault(currentChar, 0) + 1);
/* If the number of distinct characters
exceeds k, shrink the window from the left*/
while (mpp.size() > k) {
// Decrement frequency of character at left pointer
char leftChar = s.charAt(l);
mpp.put(leftChar, mpp.get(leftChar) - 1);
if (mpp.get(leftChar) == 0) {
/* Remove character from map
if its frequency becomes zero*/
mpp.remove(leftChar);
}
// Move left pointer to the right
l++;
}
/* Update maximum length of substring with
at most k distinct characters found so far*/
if (mpp.size() <= k) {
maxLen = Math.max(maxLen, r - l + 1);
}
// Move right pointer
r++;
}
// Return the maximum length found
return maxLen;
}
public static void main(String[] args) {
String s = "aaabbccd";
//Create an instance of Solution class
Solution sol = new Solution();
int res = sol.kDistinctChar(s, 2);
// Output the result
System.out.println("The maximum length of substring with at most 2 distinct characters is: " + res);
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
class Solution:
""" Function to find the length of the longest
substring with at most k distinct characters """
def kDistinctChar(self, s, k):
""" Initialize left pointer, right pointer,
and maximum length of substring"""
l, r, maxLen = 0, 0, 0
# Hash map to store character frequencies
mpp = {}
while r < len(s):
# Increment frequency of current character
if s[r] in mpp:
mpp[s[r]] += 1
else:
mpp[s[r]] = 1
""" If the number of distinct characters
exceeds k, shrink the window from the left"""
while len(mpp) > k:
# Decrement frequency of character at left pointer
mpp[s[l]] -= 1
if mpp[s[l]] == 0:
""" Remove character from map
if its frequency becomes zero"""
del mpp[s[l]]
# Move left pointer to the right
l += 1
""" Update maximum length of substring with
at most k distinct characters found so far"""
if len(mpp) <= k:
maxLen = max(maxLen, r - l + 1)
# Move right pointer
r += 1
# Return the maximum length found
return maxLen
if __name__ == "__main__":
s = "aaabbccd"
#Create an instance of Solution class
sol = Solution()
res = sol.kDistinctChar(s, 2)
# Output the result
print(f"The maximum length of substring with at most 2 distinct characters is: {res}")
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
class Solution {
/* Function to find the length of the longest
substring with at most k distinct characters*/
kDistinctChar(s, k) {
/* Initialize left pointer, right pointer,
and maximum length of substring*/
let l = 0, r = 0, maxLen = 0;
// Hash map to store character frequencies
let mpp = new Map();
while (r < s.length) {
// Increment frequency of current character
if (mpp.has(s[r])) {
mpp.set(s[r], mpp.get(s[r]) + 1);
} else {
mpp.set(s[r], 1);
}
/* If the number of distinct characters
exceeds k, shrink the window from the left*/
while (mpp.size > k) {
// Decrement frequency of character at left pointer
if (mpp.has(s[l])) {
mpp.set(s[l], mpp.get(s[l]) - 1);
if (mpp.get(s[l]) === 0) {
/* Remove character from map if
its frequency becomes zero*/
mpp.delete(s[l]);
}
}
// Move left pointer to the right
l++;
}
/* Update maximum length of substring with
at most k distinct characters found so far*/
if (mpp.size <= k) {
maxLen = Math.max(maxLen, r - l + 1);
}
// Move right pointer
r++;
}
// Return the maximum length found
return maxLen;
}
}
// Main function to test the solution
let s = "aaabbccd";
//Create an instance of Solution class
let sol = new Solution();
let res = sol.kDistinctChar(s, 2);
// Output the result
console.log(`The maximum length of substring with at most 2 distinct characters is: ${res}`);
Complexity Analysis:
Time Complexity:O(2N), where N is the size of the array. As the other while loop runs for N time and the inner while loop runs for N time in total throghto the program. Ignore the contribution of map data structure in the time complexity as size of the map is extremely small.Space Complexity: O(k) , as at most the map data structure is holding k elements.
Intuition:
The idea here is to use the sliding window approach by avoiding the additional O(N) time complexity incurred when shifting the window entirely in the Better solution, to ensure that no more than k distinct characters occurs in the current substring. Instead of moving the left pointer (l) completely till the distinct character comes under given limit, shift the window by one position at a time. This way the extra while loop used in Optimal I approach can be eliminated.
Approach:
l and r pointers to 0 to represent the left and right boundaries of the current window, maxLen is initialized to 0 to keep track of the maximum length of substring with at most k distinct characters and mpp (unordered_map) is used to track the count of each character in the current sliding window.
Dry Run:
Please refer to the video for complete dry-run.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to find the maximum length of
substring with at most k distinct characters */
int kDistinctChar(string& s, int k) {
// Length of the input string
int n = s.size();
/* Variable to store the
maximum length of substring*/
int maxLen = 0;
/* Map to track the count of each
character in the current window*/
unordered_map<char, int> mpp;
// Pointers for the sliding window approach
int l = 0, r = 0;
while(r < n){
mpp[s[r]]++;
/* If number of different characters exceeds
k, shrink the window from the left*/
if(mpp.size() > k){
mpp[s[l]]--;
if(mpp[s[l]] == 0){
mpp.erase(s[l]);
}
l++;
}
/* If number of different characters
is at most k, update maxLen*/
if(mpp.size() <= k){
maxLen = max(maxLen, r - l + 1);
}
r++;
}
// Return the maximum length
return maxLen;
}
};
int main() {
string s = "aaabbccd";
int k = 2;
// Create an instance of Solution class
Solution sol;
int length = sol.kDistinctChar(s, k);
// Print the result
cout << "Maximum length of substring with at most " << k << " distinct characters: " << length << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
import java.util.*;
class Solution {
/* Function to find the maximum length of
substring with at most k distinct characters */
public int kDistinctChar(String s, int k) {
// Length of the input string
int n = s.length();
/* Variable to store the
maximum length of substring */
int maxLen = 0;
/* Map to track the count of each
character in the current window */
HashMap<Character, Integer> mpp = new HashMap<>();
// Pointers for the sliding window approach
int l = 0, r = 0;
while(r < n){
char charR = s.charAt(r);
mpp.put(charR, mpp.getOrDefault(charR, 0) + 1);
/* If number of different characters exceeds
k, shrink the window from the left*/
if(mpp.size() > k){
char charL = s.charAt(l);
mpp.put(charL, mpp.get(charL) - 1);
if(mpp.get(charL) == 0){
mpp.remove(charL);
}
l++;
}
/* If number of different characters
is at most k, update maxLen*/
if(mpp.size() <= k){
maxLen = Math.max(maxLen, r - l + 1);
}
r++;
}
// Return the maximum length
return maxLen;
}
public static void main(String[] args) {
String s = "aaabbccd";
int k = 2;
// Create an instance of Solution class
Solution sol = new Solution();
int length = sol.kDistinctChar(s, k);
// Print the result
System.out.println("Maximum length of substring with at most " + k + " distinct characters: " + length);
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
class Solution:
""" Function to find the maximum length of
substring with at most k distinct characters """
def kDistinctChar(self, s, k):
# Length of the input string
n = len(s)
# Variable to store the
# maximum length of substring
maxLen = 0
# Map to track the count of each
# character in the current window
mpp = {}
# Pointers for the sliding window approach
l, r = 0, 0
while r < n:
charR = s[r]
mpp[charR] = mpp.get(charR, 0) + 1
# If number of different characters exceeds
# k, shrink the window from the left
if len(mpp) > k:
charL = s[l]
mpp[charL] -= 1
if mpp[charL] == 0:
del mpp[charL]
l += 1
# If number of different characters
# is at most k, update maxLen
if len(mpp) <= k:
maxLen = max(maxLen, r - l + 1)
r += 1
# Return the maximum length
return maxLen
if __name__ == "__main__":
s = "aaabbccd"
k = 2
# Create an instance of Solution class
sol = Solution()
length = sol.kDistinctChar(s, k)
# Print the result
print(f"Maximum length of substring with at most {k} distinct characters: {length}")
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
class Solution {
/*Function to find the maximum length of
substring with at most k distinct characters*/
kDistinctChar(s, k) {
// Length of the input string
let n = s.length;
/* Variable to store the
maximum length of substring */
let maxLen = 0;
/* Map to track the count of each
character in the current window */
let mpp = new Map();
// Pointers for the sliding window approach
let l = 0, r = 0;
while(r < n){
let charR = s[r];
mpp.set(charR, (mpp.get(charR) || 0) + 1);
/* If number of different characters exceeds
k, shrink the window from the left*/
if(mpp.size > k){
let charL = s[l];
mpp.set(charL, mpp.get(charL) - 1);
if(mpp.get(charL) === 0){
mpp.delete(charL);
}
l++;
}
/* If number of different characters
is at most k, update maxLen*/
if(mpp.size <= k){
maxLen = Math.max(maxLen, r - l + 1);
}
r++;
}
// Return the maximum length
return maxLen;
}
}
// Main function
let sol = new Solution();
let s = "aaabbccd";
let k = 2;
let len = sol.kDistinctChar(s, k);
// Print the result
console.log(`Maximum length of substring with at most ${k} distinct characters: ${len}`);
Complexity Analysis:
Time Complexity:O(N), where N is the size of the array. As the other while loop runs for N times only. Ignore the contribution of map data structure in the time complexity as size of the map is extremely small.Space Complexity: O(k) , as at most the map data structure is holding k elements.
Frequently Occurring Doubts
Q: What if the string contains fewer than k distinct characters?
A: If the string contains fewer than k distinct characters, the entire string is the longest substring. The result is the length of the string.
Q: Why use a sliding window approach?
A: The sliding window ensures that each character is processed at most twice (once when added and once when removed), resulting in an efficient O(n) solution.
Interview Followup Questions
Q: How would you modify the solution to handle dynamic k values during traversal?
A: Dynamically adjust the value of k as you process the string by recalculating the valid window boundaries whenever k changes.
Q: What if the input string contains spaces or special characters?
A: Spaces and special characters are treated like any other character and can be part of the substring if their inclusion satisfies the k-distinct condition.
Notes
Code
✅ Testcase
Input: {'k': '2', 's': 'aababbcaacc'}
Expected:
6
6
Actual: -
Time: -
sec
Status: Waiting
Input: {'k': '3', 's': 'abcddefg'}
Expected:
4
4
Actual: -
Time: -
sec
Status: Waiting
Input: {'k': '3', 's': 'abcdeacade'}
Expected:
4
4
Actual: -
Time: -
sec
Status: Waiting