3572. Count Substrings That Can Be Rearranged To Contain A String Ii¶

3572. Count Substrings That Can Be Rearranged to Contain a String II

Hard

You are given two strings word1 and word2.

A string x is called valid if x can be rearranged to have word2 as a prefix.

Return the total number of valid substrings of word1.

Note that the memory limits in this problem are smaller than usual, so you must implement a solution with a linear runtime complexity.

Example 1:

Input: word1 = "bcca", word2 = "abc"

Output: 1

Explanation:

The only valid substring is "bcca" which can be rearranged to "abcc" having "abc" as a prefix.

Example 2:

Input: word1 = "abcabc", word2 = "abc"

Output: 10

Explanation:

All the substrings except substrings of size 1 and size 2 are valid.

Example 3:

Input: word1 = "abcabc", word2 = "aaabc"

Output: 0

Constraints:

1 <= word1.length <= 10⁶
1 <= word2.length <= 10⁴
word1 and word2 consist only of lowercase English letters.

Solution¶

class Solution {
    public long validSubstringCount(String s1, String s2) {
        long ans = 0;
        int[] first = new int[26];
        for(int i = 0; i < s2.length(); i++) first[s2.charAt(i)-'a']++;
        int n = s1.length();
        int[] second = new int[26];
        for(int i = 0, j = 0; i < n; i++) {
            while(j < n && !check(first, second)) {
                second[s1.charAt(j)-'a']++;
                j++;
            }
            if(check(first, second))
                ans += n - j + 1;
            second[s1.charAt(i) - 'a']--;
        }
        return ans;
    }

    private boolean check(int[] a, int[] b) {
        for(int i = 0; i < a.length; i++) {
            if(a[i] > b[i]) return false;
        }
        return true;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]