Q13 PepCoding | Count Of Substrings With Exactly K Unique Characters
Wed Jan 25 2023 05:53:03 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
import java.util.*;
public class Main {
public static int solution(String s, int k){
return atmostK_subtrings(s , k) - atmostK_subtrings(s , k-1);
}
public static int atmostK_subtrings(String s , int k){
HashMap<Character,Integer> map1 = new HashMap<>();
int ans = 0 ;
//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++;
}
//adding all substrings of the current unique substring
ans += i - j+1;
}
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/count-of-substrings-with-exactly-k-unique-characters-official/ojquestion
Comments