Given a string you need to print longest possible substring that has exactly M unique characters. If there is more than one substring of longest possible length, then print any one of them.
Examples:
Input: Str = “aabbcc”, k = 1
Output: 2
Explanation: Max substring can be any one from {“aa” , “bb” , “cc”}.Input: Str = “aabbcc”, k = 2
Output: 4
Explanation: Max substring can be any one from {“aabb” , “bbcc”}.Input: Str = “aabbcc”, k = 3
Output: 6
Explanation:
There are substrings with exactly 3 unique characters
{“aabbcc” , “abbcc” , “aabbc” , “abbc” }
Max is “aabbcc” with length 6.Input: Str = “aaabbb”, k = 3
Output: Not enough unique characters
Explanation: There are only two unique characters, thus show error message.
Source: Google Interview Question.
Method 1 (Brute Force)
If the length of string is n, then there can be n*(n+1)/2 possible substrings. A simple way is to generate all the substring and check each one whether it has exactly k unique characters or not. If we apply this brute force, it would take O(n2) to generate all substrings and O(n) to do a check on each one. Thus overall it would go O(n3).
We can further improve this solution by creating a hash table and while generating the substrings, check the number of unique characters using that hash table. Thus it would improve up to O(n2).
C++
// C++ program to find the longest substring// with k unique characters in a given string#include <bits/stdc++.h>using namespace std;// Function to calculate length of// longest substring with k charactersvoid longestKSubstr(string s, int k){ int n = s.length(); int answer = -1; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= n; j++) { unordered_set<char> distinct(s.begin() + i, s.begin() + j); if (distinct.size() == k) { answer = max(answer, j - i); } } } cout << answer;}// Driver functionint main(){ string s = "aabacbebebe"; int k = 3; // Function Call longestKSubstr(s, k); return 0;} |
Java
// Java program to find the longest substring// with k unique characters in a given stringimport java.util.*;public class GFG { // Function to calculate length of // longest substring with k characters static void longestKSubstr(String s, int k) { int n = s.length(); int answer = -1; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= n; j++) { HashSet<Character> distinct = new HashSet<Character>(); for (int x = i; x < j; x++) { distinct.add(s.charAt(x)); } if (distinct.size() == k) { answer = Math.max(answer, j - i); } } } System.out.println(answer); } public static void main(String[] args) { String s = "aabacbebebe"; int k = 3; // Function Call longestKSubstr(s, k); }}// This code is contributed by garg28harsh. |
C#
// C# program to find ceil of a given value in BSTusing System;using System.Collections.Generic;public class GFG { // Function to calculate length of // longest substring with k characters static void longestKSubstr(string s, int k) { int n = s.Length; int answer = -1; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= n; j++) { HashSet<char> distinct = new HashSet<char>(); for (int x = i; x < j; x++) { distinct.Add(s[x]); } if (distinct.Count == k) { answer = Math.Max(answer, j - i); } } } Console.WriteLine(answer); } public static void Main(string[] args) { String s = "aabacbebebe"; int k = 3; // Function Call longestKSubstr(s, k); }}// This code is contributed by karandeep1234 |
Python3
# Python program to find the longest substring# with k unique characters in a given string# Function to calculate length of# longest substring with k charactersdef longestKSubstr(s, k): n = len(s) answer = -1 for i in range(n): for j in range(i+1, n+1): distinct = set(s[i:j]) if len(distinct) == k: answer = max(answer, j - i) print(answer)s = "aabacbebebe"k = 3# Function CalllongestKSubstr(s, k) |
Javascript
// JavaScript function to find the longest substring// with k unique characters in a given stringfunction longestKSubstr(s, k) { let n = s.length; let answer = -1; for (let i = 0; i < n; i++) { for (let j = i + 1; j <= n; j++) { let distinct = new Set(); for (let x = i; x < j; x++) { distinct.add(s.charAt(x)); } if (distinct.size === k) { answer = Math.max(answer, j - i); } } } console.log(answer);}let s = "aabacbebebe";let k = 3;// Function calllongestKSubstr(s, k);//This code is contributed by shivamsharma215 |
Output
7
Time Complexity: O(n^2)
Auxiliary Space: O(n)
Method 2 (Linear Time)
The problem can be solved in O(n). Idea is to maintain a window and add elements to the window till it contains less or equal k, update our result if required while doing so. If unique elements exceeds than required in window, start removing the elements from left side.
Below are the implementations of above. The implementations assume that the input string alphabet contains only 26 characters (from ‘a’ to ‘z’). The code can be easily extended to 256 characters.
C++
// C++ program to find the longest substring with k unique// characters in a given string#include <iostream>#include <cstring>#define MAX_CHARS 26using namespace std;// This function calculates number of unique characters// using a associative array count[]. Returns true if// no. of characters are less than required else returns// false.bool isValid(int count[], int k){ int val = 0; for (int i=0; i<MAX_CHARS; i++) if (count[i] > 0) val++; // Return true if k is greater than or equal to val return (k >= val);}// Finds the maximum substring with exactly k unique charsvoid kUniques(string s, int k){ int u = 0; // number of unique characters int n = s.length(); // Associative array to store the count of characters int count[MAX_CHARS]; memset(count, 0, sizeof(count)); // Traverse the string, Fills the associative array // count[] and count number of unique characters for (int i=0; i<n; i++) { if (count[s[i]-'a']==0) u++; count[s[i]-'a']++; } // If there are not enough unique characters, show // an error message. if (u < k) { cout << "Not enough unique characters"; return; } // Otherwise take a window with first element in it. // start and end variables. int curr_start = 0, curr_end = 0; // Also initialize values for result longest window int max_window_size = 1, max_window_start = 0; // Initialize associative array count[] with zero memset(count, 0, sizeof(count)); count[s[0]-'a']++; // put the first character // Start from the second character and add // characters in window according to above // explanation for (int i=1; i<n; i++) { // Add the character 's[i]' to current window count[s[i]-'a']++; curr_end++; // If there are more than k unique characters in // current window, remove from left side while (!isValid(count, k)) { count[s[curr_start]-'a']--; curr_start++; } // Update the max window size if required if (curr_end-curr_start+1 > max_window_size) { max_window_size = curr_end-curr_start+1; max_window_start = curr_start; } } cout << "Max substring is : " << s.substr(max_window_start, max_window_size) << " with length " << max_window_size << endl;}// Driver functionint main(){ string s = "aabacbebebe"; int k = 3; kUniques(s, k); return 0;} |
Java
import java.util.Arrays; // Java program to find the longest substring with k unique // characters in a given string class GFG { final static int MAX_CHARS = 26; // This function calculates number // of unique characters // using a associative array // count[]. Returns true if // no. of characters are less // than required else returns // false. static boolean isValid(int count[], int k) { int val = 0; for (int i = 0; i < MAX_CHARS; i++) { if (count[i] > 0) { val++; } } // Return true if k is greater // than or equal to val return (k >= val); } // Finds the maximum substring // with exactly k unique chars static void kUniques(String s, int k) { int u = 0; int n = s.length(); // Associative array to store // the count of characters int count[] = new int[MAX_CHARS]; Arrays.fill(count, 0); // Traverse the string, Fills // the associative array // count[] and count number // of unique characters for (int i = 0; i < n; i++) { if (count[s.charAt(i) - 'a'] == 0) { u++; } count[s.charAt(i) - 'a']++; } // If there are not enough // unique characters, show // an error message. if (u < k) { System.out.print("Not enough unique characters"); return; } // Otherwise take a window with // first element in it. // start and end variables. int curr_start = 0, curr_end = 0; // Also initialize values for // result longest window int max_window_size = 1; int max_window_start = 0; // Initialize associative // array count[] with zero Arrays.fill(count, 0); // put the first character count[s.charAt(0) - 'a']++; // Start from the second character and add // characters in window according to above // explanation for (int i = 1; i < n; i++) { // Add the character 's[i]' // to current window count[s.charAt(i) - 'a']++; curr_end++; // If there are more than k // unique characters in // current window, remove from left side while (!isValid(count, k)) { count[s.charAt(curr_start) - 'a']--; curr_start++; } // Update the max window size if required if (curr_end - curr_start + 1 > max_window_size) { max_window_size = curr_end - curr_start + 1; max_window_start = curr_start; } } System.out.println("Max substring is : " + s.substring(max_window_start, max_window_start + max_window_size) + " with length " + max_window_size); } // Driver Code static public void main(String[] args) { String s = "aabacbebebe"; int k = 3; kUniques(s, k); } } // This code is contributed by 29AjayKumar |
Python3
# Python program to find the longest substring with k unique # characters in a given string MAX_CHARS = 26# This function calculates number of unique characters # using a associative array count[]. Returns true if # no. of characters are less than required else returns # false. def isValid(count, k): val = 0 for i in range(MAX_CHARS): if count[i] > 0: val += 1 # Return true if k is greater than or equal to val return (k >= val) # Finds the maximum substring with exactly k unique characters def kUniques(s, k): u = 0 # number of unique characters n = len(s) # Associative array to store the count count = [0] * MAX_CHARS # Traverse the string, fills the associative array # count[] and count number of unique characters for i in range(n): if count[ord(s[i])-ord('a')] == 0: u += 1 count[ord(s[i])-ord('a')] += 1 # If there are not enough unique characters, show # an error message. if u < k: print ("Not enough unique characters") return # Otherwise take a window with first element in it. # start and end variables. curr_start = 0 curr_end = 0 # Also initialize values for result longest window max_window_size = 1 max_window_start = 0 # Initialize associative array count[] with zero count = [0] * len(count) count[ord(s[0])-ord('a')] += 1 # put the first character # Start from the second character and add # characters in window according to above # explanation for i in range(1,n): # Add the character 's[i]' to current window count[ord(s[i])-ord('a')] += 1 curr_end+=1 # If there are more than k unique characters in # current window, remove from left side while not isValid(count, k): count[ord(s[curr_start])-ord('a')] -= 1 curr_start += 1 # Update the max window size if required if curr_end-curr_start+1 > max_window_size: max_window_size = curr_end-curr_start+1 max_window_start = curr_start print ("Max substring is : " + s[max_window_start:max_window_start + max_window_size] + " with length " + str(max_window_size))# Driver function s = "aabacbebebe"k = 3kUniques(s, k) # This code is contributed by BHAVYA JAIN |
C#
// C# program to find the longest substring with k unique // characters in a given string using System;public class GFG{ static int MAX_CHARS = 26; // This function calculates number // of unique characters // using a associative array // count[]. Returns true if // no. of characters are less // than required else returns // false. static bool isValid(int[] count, int k) { int val = 0; for (int i = 0; i < MAX_CHARS; i++) { if (count[i] > 0) { val++; } } // Return true if k is greater // than or equal to val return (k >= val); } // Finds the maximum substring // with exactly k unique chars static void kUniques(string s, int k) { int u = 0; int n = s.Length; // Associative array to store // the count of characters int[] count = new int[MAX_CHARS]; Array.Fill(count, 0); // Traverse the string, Fills // the associative array // count[] and count number // of unique characters for (int i = 0; i < n; i++) { if (count[s[i] - 'a'] == 0) { u++; } count[s[i] - 'a']++; } // If there are not enough // unique characters, show // an error message. if (u < k) { Console.Write("Not enough unique characters"); return; } // Otherwise take a window with // first element in it. // start and end variables. int curr_start = 0, curr_end = 0; // Also initialize values for // result longest window int max_window_size = 1; int max_window_start = 0; // Initialize associative // array count[] with zero Array.Fill(count, 0); // put the first character count[s[0] - 'a']++; // Start from the second character and add // characters in window according to above // explanation for (int i = 1; i < n; i++) { // Add the character 's[i]' // to current window count[s[i] - 'a']++; curr_end++; // If there are more than k // unique characters in // current window, remove from left side while (!isValid(count, k)) { count[s[curr_start] - 'a']--; curr_start++; } // Update the max window size if required if (curr_end - curr_start + 1 > max_window_size) { max_window_size = curr_end - curr_start + 1; max_window_start = curr_start; } } Console.WriteLine("Max substring is : "+ s.Substring(max_window_start, max_window_size) + " with length " + max_window_size); } // Driver code static public void Main (){ string s = "aabacbebebe"; int k = 3; kUniques(s, k); }}// This code is contributed by avanitrachhadiya2155 |
Javascript
<script>// Javascript program to find the longest// substring with k unique characters in// a given stringlet MAX_CHARS = 26;// This function calculates number of // unique characters using a associative// array count[]. Returns true if no. of // characters are less than required else // returns false.function isValid(count, k){ let val = 0; for(let i = 0; i < MAX_CHARS; i++) { if (count[i] > 0) { val++; } } // Return true if k is greater // than or equal to val return (k >= val);}// Finds the maximum substring // with exactly k unique charsfunction kUniques(s,k){ // Number of unique characters let u = 0; let n = s.length; let count = new Array(MAX_CHARS); for(let i = 0; i < MAX_CHARS; i++) { count[i] = 0; } // Traverse the string, Fills // the associative array // count[] and count number // of unique characters for(let i = 0; i < n; i++) { if (count[s[i].charCodeAt(0) - 'a'.charCodeAt(0)] == 0) { u++; } count[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; } // If there are not enough // unique characters, show // an error message. if (u < k) { document.write("Not enough unique characters"); return; } // Otherwise take a window with // first element in it. // start and end variables. let curr_start = 0, curr_end = 0; // Also initialize values for // result longest window let max_window_size = 1; let max_window_start = 0; // Initialize associative // array count[] with zero for(let i = 0; i < MAX_CHARS; i++) { count[i] = 0; } // put the first character count[s[0].charCodeAt(0) - 'a'.charCodeAt(0)]++; // Start from the second character and add // characters in window according to above // explanation for(let i = 1; i < n; i++) { // Add the character 's[i]' // to current window count[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; curr_end++; // If there are more than k // unique characters in // current window, remove from left side while (!isValid(count, k)) { count[s[curr_start].charCodeAt(0) - 'a'.charCodeAt(0)]--; curr_start++; } // Update the max window size if required if (curr_end - curr_start + 1 > max_window_size) { max_window_size = curr_end - curr_start + 1; max_window_start = curr_start; } } document.write("Max substring is : " + s.substring(max_window_start, max_window_start + max_window_size + 1) + " with length " + max_window_size);}// Driver Codelet s = "aabacbebebe";let k = 3;kUniques(s, k);// This code is contributed by rag2127</script> |
Output
Max substring is : cbebebe with length 7
Time Complexity: Considering function “isValid()” takes constant time, time complexity of above solution is O(n).
Auxiliary Space: O(MAX_CHARS).
This article is contributed by Gaurav Sharma. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
ANOTHER APPROACH:(Linear Time)
INTUITION :
- We declare a Map<Character,Integer> data structure to store frequency of characters.
- Here we use acquire and release property .
- In this we declare two pointers i and j, we traverse from i pointer and acquire characters until map size is greater than K. When map size get equals to k we store the length of i-j in a variable and traverse forward.
- Once map size exceeds K,then we start releasing characters from map with the help of j pointer till map size again equals K, and we store the length and compare with previous length and this way the algorithm continues.
Implementation:
C++
#include <iostream>#include <unordered_map>using namespace std;int longestKSubstr(string s, int k){ int i = 0; int j = 0; int ans = -1; unordered_map<char, int> mp; while (j < s.size()) { mp[s[j]]++; while (mp.size() > k) { mp[s[i]]--; if (mp[s[i]] == 0) mp.erase(s[i]); i++; } if (mp.size() == k) { ans = max(ans, j - i + 1); } j++; } return ans;}int main(){ string s = "aabacbebebe"; int k = 3; cout << longestKSubstr(s, k) << endl; return 0;} |
Java
//Java program to find the longest substring with k unique characters in a given stringimport java.io.*;import java.util.*;class GFG { public static int longestkSubstr(String S, int k) { // code here Map<Character, Integer> map = new HashMap<>(); int i = -1; int j = -1; int ans = -1; while (true) { boolean flag1 = false; boolean flag2 = false; while (i < S.length() - 1) { flag1 = true; i++; char ch = S.charAt(i); map.put(ch, map.getOrDefault(ch, 0) + 1); if (map.size() < k) continue; else if (map.size() == k) { int len = i - j; ans = Math.max(len, ans); } else break; } while (j < i) { flag2 = true; j++; char ch = S.charAt(j); if (map.get(ch) == 1) map.remove(ch); else map.put(ch, map.get(ch) - 1); if (map.size() == k) { int len = i - j; ans = Math.max(ans, len); break; } else if (map.size() > k) continue; } if (flag1 == false && flag2 == false) break; } return ans; } public static void main(String[] args) { String s = "aabacbebebe"; int k = 3; // Function Call int ans = longestkSubstr(s, k); System.out.println(ans); }}// This code is contributed by Raunak Singh |
Python3
def longestkSubstr(S, k): # Create an empty dictionary to store character counts map = {} # Initialize two pointers i and j to -1 i = -1 j = -1 # Initialize ans to -1 ans = -1 # Loop until break statement is reached while True: # Initialize two flags to False flag1 = False flag2 = False # Loop until i reaches end of string S while i < len(S) - 1: # Set flag1 to True flag1 = True # Increment i and get character at index i i += 1 ch = S[i] # Add character count to dictionary map[ch] = map.get(ch, 0) + 1 # If number of unique characters is less than k, continue loop if len(map) < k: continue # If number of unique characters is equal to k, update ans if necessary and continue loop elif len(map) == k: len_ = i - j ans = max(len_, ans) # If number of unique characters is greater than k, break loop else: break # Loop until j reaches i while j < i: # Set flag2 to True flag2 = True # Increment j and get character at index j j += 1 ch = S[j] # If character count is 1, remove character from dictionary if map[ch] == 1: del map[ch] # If character count is greater than 1, decrement character # count in dictionary else: map[ch] -= 1 # If number of unique characters is equal to k, # update ans if necessary and break loop if len(map) == k: len_ = i - j ans = max(ans, len_) break # If number of unique characters is greater than k, continue loop elif len(map) > k: continue # If both flags are False, break outer loop (while True) if not flag1 and not flag2: break return ans# Test case inputs and function calls = "aabacbebebe"k = 3ans = longestkSubstr(s, k)print(ans) |
C#
using System;using System.Collections.Generic;class MainClass { public static int LongestKSubstr(string s, int k) { int i = 0; int j = 0; int ans = -1; Dictionary<char, int> mp = new Dictionary<char, int>(); while (j < s.Length) { if (mp.ContainsKey(s[j])) { mp[s[j]]++; } else { mp[s[j]] = 1; } while (mp.Count > k) { mp[s[i]]--; if (mp[s[i]] == 0) { mp.Remove(s[i]); } i++; } if (mp.Count == k) { ans = Math.Max(ans, j - i + 1); } j++; } return ans; } public static void Main() { string s = "aabacbebebe"; int k = 3; Console.WriteLine(LongestKSubstr(s, k)); }} |
Javascript
function longestKSubstr(s, k) { let i = 0; let j = 0; let ans = -1; let mp = new Map(); while (j < s.length) { mp.set(s[j], (mp.get(s[j]) || 0) + 1); while (mp.size > k) { mp.set(s[i], mp.get(s[i]) - 1); if (mp.get(s[i]) === 0) { mp.delete(s[i]); } i++; } if (mp.size === k) { ans = Math.max(ans, j - i + 1); } j++; } return ans;}let s = "aabacbebebe";let k = 3;console.log(longestKSubstr(s, k)); |
Output
7
Time Complexity: O(|S|)
Space Complexity:O(|S|)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
