Given a string str and an integer K, the task is to print the length of the longest possible substring that has exactly K unique characters. If there is more than one substring of the longest possible length, then print any one of them or print -1 if there is no such substring possible.
Examples:
Input: str = “aabacbebebe”, K = 3
Output: 7
“cbebebe” is the required substring.Input: str = “aabc”, K = 4
Output: -1
Approach: An approach to solve this problem has been discussed in this article. In this article, a binary search based approach will be discussed. Binary search will be applied to the length of the substring which has at least K unique characters. Let’s say we try for length len and check whether a substring of size len is there which is having at least k unique characters. If it is possible, then try to maximize the size by searching for this length to the maximum possible length, i.e. the size of the input string. If it is not possible, then search for a lower size len.
To check that the length given by binary search will have k unique characters, a set can be used to insert all the characters, and then if the size of the set is less than k then the answer is not possible, else the answer given by the binary search is the max answer.
Binary search is applicable here because it is known if for some len the answer is possible and we want to maximize the len so the search domain changes and we search from this len to n.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if there// is a substring of length len// with <=k unique charactersbool isValidLen(string s, int len, int k){ // Size of the string int n = s.size(); // Map to store the characters // and their frequency unordered_map<char, int> mp; int right = 0; // Update the map for the // first substring while (right < len) { mp[s[right]]++; right++; } if (mp.size() <= k) return true; // Check for the rest of the substrings while (right < n) { // Add the new character mp[s[right]]++; // Remove the first character // of the previous window mp[s[right - len]]--; // Update the map if (mp[s[right - len]] == 0) mp.erase(s[right - len]); if (mp.size() <= k) return true; right++; } return mp.size() <= k;}// Function to return the length of the// longest substring which has K// unique charactersint maxLenSubStr(string s, int k){ // Check if the complete string // contains K unique characters set<char> uni; for (auto x : s) uni.insert(x); if (uni.size() < k) return -1; // Size of the string int n = s.size(); // Apply binary search int lo = -1, hi = n + 1; while (hi - lo > 1) { int mid = lo + hi >> 1; if (isValidLen(s, mid, k)) lo = mid; else hi = mid; } return lo;}// Driver codeint main(){ string s = "aabacbebebe"; int k = 3; cout << maxLenSubStr(s, k); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG { // Function that returns true if there // is a subString of length len // with <=k unique characters static boolean isValidLen(String s, int len, int k) { // Size of the String int n = s.length(); // Map to store the characters // and their frequency Map<Character, Integer> mp = new HashMap<Character, Integer>(); int right = 0; // Update the map for the // first subString while (right < len) { if (mp.containsKey(s.charAt(right))) { mp.put(s.charAt(right), mp.get(s.charAt(right)) + 1); } else { mp.put(s.charAt(right), 1); } right++; } if (mp.size() <= k) return true; // Check for the rest of the subStrings while (right < n) { // Add the new character if (mp.containsKey(s.charAt(right))) { mp.put(s.charAt(right), mp.get(s.charAt(right)) + 1); } else { mp.put(s.charAt(right), 1); } // Remove the first character // of the previous window if (mp.containsKey(s.charAt(right - len))) { mp.put(s.charAt(right - len), mp.get(s.charAt(right - len)) - 1); } // Update the map if (mp.get(s.charAt(right - len)) == 0) mp.remove(s.charAt(right - len)); if (mp.size() <= k) return true; right++; } return mp.size() <= k; } // Function to return the length of the // longest subString which has K // unique characters static int maxLenSubStr(String s, int k) { // Check if the complete String // contains K unique characters Set<Character> uni = new HashSet<Character>(); for (Character x : s.toCharArray()) uni.add(x); if (uni.size() < k) return -1; // Size of the String int n = s.length(); // Apply binary search int lo = -1, hi = n + 1; while (hi - lo > 1) { int mid = lo + hi >> 1; if (isValidLen(s, mid, k)) lo = mid; else hi = mid; } return lo; } // Driver code public static void main(String[] args) { String s = "aabacbebebe"; int k = 3; System.out.print(maxLenSubStr(s, k)); }}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach# Function that returns True if there# is a sub of length len# with <=k unique charactersdef isValidLen(s, lenn, k): # Size of the n = len(s) # Map to store the characters # and their frequency mp = dict() right = 0 # Update the map for the # first sub while (right < lenn): mp[s[right]] = mp.get(s[right], 0) + 1 right += 1 if (len(mp) <= k): return True # Check for the rest of the subs while (right < n): # Add the new character mp[s[right]] = mp.get(s[right], 0) + 1 # Remove the first character # of the previous window mp[s[right - lenn]] -= 1 # Update the map if (mp[s[right - lenn]] == 0): del mp[s[right - lenn]] if (len(mp) <= k): return True right += 1 return len(mp)<= k# Function to return the length of the# longest sub which has K# unique charactersdef maxLenSubStr(s, k): # Check if the complete # contains K unique characters uni = dict() for x in s: uni[x] = 1 if (len(uni) < k): return -1 # Size of the n = len(s) # Apply binary search lo = -1 hi = n + 1 while (hi - lo > 1): mid = lo + hi >> 1 if (isValidLen(s, mid, k)): lo = mid else: hi = mid return lo# Driver codes = "aabacbebebe"k = 3print(maxLenSubStr(s, k))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG { // Function that returns true if there // is a subString of length len // with <=k unique characters static bool isValidLen(String s, int len, int k) { // Size of the String int n = s.Length; // Map to store the characters // and their frequency Dictionary<char, int> mp = new Dictionary<char, int>(); int right = 0; // Update the map for the // first subString while (right < len) { if (mp.ContainsKey(s[right])) { mp[s[right]] = mp[s[right]] + 1; } else { mp.Add(s[right], 1); } right++; } if (mp.Count <= k) return true; // Check for the rest of the subStrings while (right < n) { // Add the new character if (mp.ContainsKey(s[right])) { mp[s[right]] = mp[s[right]] + 1; } else { mp.Add(s[right], 1); } // Remove the first character // of the previous window if (mp.ContainsKey(s[right - len])) { mp[s[right - len]] = mp[s[right - len]] - 1; } // Update the map if (mp[s[right - len]] == 0) mp.Remove(s[right - len]); if (mp.Count <= k) return true; right++; } return mp.Count <= k; } // Function to return the length of the // longest subString which has K // unique characters static int maxLenSubStr(String s, int k) { // Check if the complete String // contains K unique characters HashSet<char> uni = new HashSet<char>(); foreach (char x in s.ToCharArray()) uni.Add(x); if (uni.Count < k) return -1; // Size of the String int n = s.Length; // Apply binary search int lo = -1, hi = n + 1; while (hi - lo > 1) { int mid = lo + hi >> 1; if (isValidLen(s, mid, k)) lo = mid; else hi = mid; } return lo; } // Driver code public static void Main(String[] args) { String s = "aabacbebebe"; int k = 3; Console.Write(maxLenSubStr(s, k)); }}// This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation of the approach// Function that returns true if there// is a substring of length len// with <=k unique charactersfunction isValidLen(s, len, k){ // Size of the string var n = s.length; // Map to store the characters // and their frequency var mp = new Map(); var right = 0; // Update the map for the // first substring while (right < len) { if(mp.has(s[right])) mp.set(s[right],mp.get(s[right])+1) else mp.set(s[right], 1) right++; } if (mp.size <= k) return true; // Check for the rest of the substrings while (right < n) { // Add the new character if(mp.has(s[right])) mp.set(s[right],mp.get(s[right])+1) else mp.set(s[right], 1) // Remove the first character // of the previous window if(mp.has(s[right - len])) mp.set(s[right - len], mp.get(s[right - len])-1) // Update the map if(mp.has(s[right - len]) && mp.get(s[right - len])==0) mp.delete(s[right - len]); if (mp.size <= k) return true; right++; } return mp.size <= k;}// Function to return the length of the// longest substring which has K// unique charactersfunction maxLenSubStr(s, k){ // Check if the complete string // contains K unique characters var uni = new Set(); s.split('').forEach(x => { uni.add(x); }); if (uni.size < k) return -1; // Size of the string var n = s.length; // Apply binary search var lo = -1, hi = n + 1; while (hi - lo > 1) { var mid = lo + hi >> 1; if (isValidLen(s, mid, k)) lo = mid; else hi = mid; } return lo;}// Driver codevar s = "aabacbebebe";var k = 3;document.write( maxLenSubStr(s, k));</script> |
7
The time complexity of the given program is O(N*logN), where N is the length of the input string. This is because the program uses binary search to find the maximum length of a substring with K unique characters, and the isValidLen function checks whether a substring of a given length has at most K unique characters.
The space complexity of the given program is O(N), where N is the length of the input string. This is because the program uses an unordered_map to keep track of the frequency of each character in the current substring, and the size of this map can be at most the number of unique characters in the input string, which is O(N) in the worst case. Additionally, the program uses a set to check whether the input string contains at least K unique characters, and the size of this set can also be at most O(N).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
