Problem
Pattern: number of subarray/substring with condition like sum ==k or count = k
TC: O(n)
class Solution {
public long countOfSubstrings(String word, int k) {
return Math.abs(find(word,k) - find(word,k+1));
}
public long find(String w, int k){
if(k<0) return 0;
Map<Character,Integer> map = new HashMap<>();
int left =0;
int right =0;
int con = 0;
long count=0;
while(right < w.length()){
char cr = w.charAt(right);
if(isv(cr)){
map.put(cr,map.getOrDefault(cr,0)+1);
}
else con++;
while(map.size() ==5 && con >=k){
count+= w.length()-right;
char cl = w.charAt(left);
if(isv(cl)){
int f = map.get(cl);
if(f ==1) map.remove(cl);
else map.put(cl,f-1);
}
else con--;
left++;
}
right++;
}
return count;
}
public boolean isv(char c){
return c =='a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
}
Top comments (0)