Find the longest substring with k unique characters in a given string

Last Updated : 24 Apr, 2023

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(n²) to generate all substrings and O(n) to do a check on each one. Thus overall it would go O(n³).

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 characters
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++) {
            unordered_set<char> distinct(s.begin() + i,
                                         s.begin() + j);
            if (distinct.size() == k) {
                answer = max(answer, j - i);
            }
        }
    }
   
    cout << answer;
}
 
// Driver function
int 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 string
import 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 BST
using 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 characters
def 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 Call
longestKSubstr(s, k)

Javascript

// JavaScript function to find the longest substring
// with k unique characters in a given string
function 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 call
longestKSubstr(s, k);
 
//This code is contributed by shivamsharma215

Output

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 26
using 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 chars
void 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 function
int 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 = 3
kUniques(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 string
let 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 chars
function 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 Code
let 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).

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 string
 
import 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 call
s = "aabacbebebe"
k = 3
 
ans = 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

Time Complexity: O(|S|)
Space Complexity:O(|S|)

Suggest improvement

Maximum consecutive repeating character in string

K'th Largest Element in BST when modification to BST is not allowed

Share your thoughts in the comments

Find the longest substring with k unique characters in a given string

C++

Java

C#

Python3

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?