Longest substring with K unique characters

Given a string you need to print the size of the longest possible substring that has exactly K unique characters. If there is no possible substring then print -1.

Share
Example 1
Input: S = "aabacbebebe", K = 3
Output: 7
Explanation: "cbebebe" is the longest substring with 3 unique characters.
Example 2
Input: S = "aaaa", K = 2
Output: -1
There's no substring with 2 unique characters.
Constraints:

Contents

Solution 1 - Using sliding window technique, keep track of longest substring with 'k' unique characters using a HashMap

In this approach, we will loop through characters of input string s and capture character and its count into a HashMap and when the HashMap size reached k, keep track of the longest length of substring which had k unique characters, and when the size is going out of bounds of k start removing the characters from left side of the input string.

Java
import java.util.HashMap;

public class LongestSubstringWithKUniqueChars {

    static int longestWithKUnique(String s, int k) {
        HashMap<Character, Integer> count = new HashMap<>();
        int left=0;
        int right=0;
        int longest = -1;
        while(right < s.length()) {
            char current = s.charAt(right);
            count.merge(current, 1, Integer::sum);
            if(count.size() == k) {
                longest = Math.max(longest, right - left +1);
            }
            while(count.size()>k) {
                char leftChar = s.charAt(left);
                int newCount = count.merge(leftChar, -1, Integer::sum);
                if(newCount == 0){
                    count.remove(leftChar);
                }
                left++;
            }
            right++;
        }
        return longest;
    }

    public static void main(String[] args) {
        System.out.println(longestWithKUnique("aabacbebebe", 3));
        System.out.println(longestWithKUnique("aaaa", 2));

    }
}
Complexity Analysis:

Time complexity: Above code runs in O(n) time, where n is the length of input string s.
Space complexity: O(n), since we are storing characters of input strings s and their count into a HashMap.

Above implementations source code can be found at GitHub link for Java code