Input: S = "aabacbebebe", K = 3
Output: 7
Explanation: "cbebebe" is the longest substring with 3 unique characters.
Input: S = "aaaa", K = 2
Output: -1
There's no substring with 2 unique characters.
Constraints:
- 1 <= s.length <= 105
- 1 <= K <= 26
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.
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