DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Count Substrings That Can Be Rearranged to Contain a String I

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++;
        }
        return count;
    }

    public boolean satisfy(int b[], int w[]) {

        for (int i = 0; i < 26; i++) {
            if (w[i] > b[i])
                return false;
        }
        // System.out.println(sb.toString());
        return true;
    }
}


Enter fullscreen mode Exit fullscreen mode

Top comments (0)