Optimizing String Substring Count With Efficient Algorithm
Solution: Count substrings with at least k distinct characters. Use sliding window approach, incrementing right pointer and decrementing left pointer when necessary hash values reach threshold.
Problem
class Solution {
public int numberOfSubstrings(String s, int k) {
int left =0, right = 0;
int hash[] = new int[26];
int count = 0;
while(right<s.length()){
char c= s.charAt(right);
hash[c-'a']++;
while(hash[c-'a']>=k){
count = count+1 + s.length()-1-right;
hash[s.charAt(left)-'a']--;
left++;
}
right++;
}
return count;
}
}