DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Count of Substrings Containing Every Vowel and K Consonants II

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';
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)