import java.util.HashMap;
import java.util.HashSet;
public class Solution {
public static int getLengthofLongestSubstring(int k, String s) {
// Write your code here.
return slidingWindowApproach(k, s);
}
public static int brutforceApproach(int k, String s) {
// Write your code here.
int ans = 0, n = s.length();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// i to j is a subarray
HashSet<Character> set = new HashSet<>();
int count = 0;
for (int l = i; l <= j; l++) {
char c = s.charAt(l);
set.add(c);
count++;
}
if (set.size() <= k) {
ans = Math.max(ans, count);
}
}
}
return ans;
}
public static int betterApproach(int k, String s) {
int n = s.length(), ans = 0;
for (int i = 0; i < n; i++) {
int j = i;
HashSet<Character> set = new HashSet<>();
while (j < n) {
set.add(s.charAt(j));
if (set.size() <= k) {
ans = Math.max(ans, j - i + 1);
}
j++;
}
}
return ans;
}
public static int slidingWindowApproach(int k, String s) {
int i = 0, j = 0, n = s.length(), ans = 0;
HashMap<Character, Integer> map = new HashMap<>();
while (j < n) {
char c = s.charAt(j);
while (map.size() > k) {
char temp = s.charAt(i);
map.put(temp, map.getOrDefault(temp, 0) - 1);
if (map.get(temp) <= 0) {
map.remove(temp);
}
i++;
}
map.put(c, map.getOrDefault(c, 0) + 1);
if (map.size() <= k) {
ans = Math.max(ans, j - i + 1);
}
j++;
}
return ans;
}
}