Q-12 PepCoding | Longest Substring With Exactly K Unique Characters
Wed Jan 25 2023 03:31:09 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
import java.util.*;
public class Main {
public static int solution(String str, int k){
HashMap<Character,Integer> map1 = new HashMap<>();
int ans = -1 ;
//pointers to keep track of window
int i = 0 , j = 0;
//acquiring and releasing while traversing the array
for(i = 0 ; i< s.length(); i++){
//storing in map and updating ccc
char ch = s.charAt(i);
map1.put(ch,map1.getOrDefault(ch,0)+1);
//if at any moment the substring becomes invalid we go in this loop to remove the extra character from the back
while(map1.size()>k){
//removing character & updating ccc
char temp = s.charAt(j);
//updating ccc
if(map1.get(temp) == 1)
map1.remove(temp);
else
map1.put(temp , map1.get(temp)-1);
j++;
}
//while map size == k we store maximum answer
if(map1.size() == k){
String pans = s.substring(j , i+1);
ans = Math.max(ans , pans.length());
}
}
return ans;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
String str = scn.next();
int k = scn.nextInt();
System.out.println(solution(str,k));
}
}
content_copyCOPY
https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup/hashmap-and-heaps/longest-substring-with-exactly-k-unique-characters-official/ojquestion
Comments