Optimizing Substring Count With Efficient Algorithm
Solution class counts valid substrings of word1 that can be formed using characters from word2, ensuring frequency of each character in the substring is not more than in word2.
problem
class Solution {
public long validSubstringCount(String word1, String word2) {
long count = 0;
int left = 0, right = 0;
int arr[] = new int[26];
for (int i = 0; i < word2.length(); i++) {
arr[word2.charAt(i) - 'a']++;
}
int b[] = new int[26];
while (right < word1.length()) {
b[word1.charAt(right) - 'a']++;
while(satisfy(b, arr)) {
count += word1.length() - right;
b[word1.charAt(left) - 'a']--;
left++;
}
right++;...