Skip to content

3297. Count Substrings That Can Be Rearranged to Contain a String I

Description

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.

 

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 <= 105
  • 1 <= word2.length <= 104
  • word1 and word2 consist only of lowercase English letters.

Solutions

Solution 1: Sliding Window

Thinking

A substring can be rearranged to contain \(\textit{word2}\) iff it is a supermultiset of \(\textit{word2}\). Comparing counts on every substring is too slow on a long string. Coverage is monotone: a valid window stays valid when the right end grows, and shrinking the left finds the shortest cover.

Track how many character types are still missing. The right end may decrement that count; while it is \(0\), move the left. Every start to the left of that left end paired with the current right is valid, so add the left index. One slide.

The problem is essentially to find how many substrings in \(\textit{word1}\) contain all the characters in \(\textit{word2}\). We can use a sliding window to handle this.

First, if the length of \(\textit{word1}\) is less than the length of \(\textit{word2}\), then it is impossible for \(\textit{word1}\) to contain all the characters of \(\textit{word2}\), so we directly return \(0\).

Next, we use a hash table or an array of length \(26\) called \(\textit{cnt}\) to count the occurrences of characters in \(\textit{word2}\). Then, we use \(\textit{need}\) to record how many more characters are needed to meet the condition, initialized to the length of \(\textit{cnt}\).

We then use a sliding window \(\textit{win}\) to record the occurrences of characters in the current window. We use \(\textit{ans}\) to record the number of substrings that meet the condition, and \(\textit{l}\) to record the left boundary of the window.

We traverse each character in \(\textit{word1}\). For the current character \(c\), we add it to \(\textit{win}\). If the value of \(\textit{win}[c]\) equals \(\textit{cnt}[c]\), it means the current window already contains one of the characters in \(\textit{word2}\), so we decrement \(\textit{need}\) by one. If \(\textit{need}\) equals \(0\), it means the current window contains all the characters in \(\textit{word2}\). We need to shrink the left boundary of the window until \(\textit{need}\) is greater than \(0\). Specifically, if \(\textit{win}[\textit{word1}[l]]\) equals \(\textit{cnt}[\textit{word1}[l]]\), it means the current window contains one of the characters in \(\textit{word2}\). After shrinking the left boundary, it no longer meets the condition, so we increment \(\textit{need}\) by one and decrement \(\textit{win}[\textit{word1}[l]]\) by one. Then, we increment \(\textit{l}\) by one. At this point, the window is \([l, r]\). For any \(0 \leq l' < l\), \([l', r]\) are substrings that meet the condition, and there are \(l\) such substrings, which we add to the answer.

After traversing all characters in \(\textit{word1}\), we get the answer.

The time complexity is \(O(n + m)\), where \(n\) and \(m\) are the lengths of \(\textit{word1}\) and \(\textit{word2}\), respectively. The space complexity is \(O(|\Sigma|)\), where \(\Sigma\) is the character set. Here, it is the set of lowercase letters, so the space complexity is constant.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        if len(word1) < len(word2):
            return 0
        cnt = Counter(word2)
        need = len(cnt)
        ans = l = 0
        win = Counter()
        for c in word1:
            win[c] += 1
            if win[c] == cnt[c]:
                need -= 1
            while need == 0:
                if win[word1[l]] == cnt[word1[l]]:
                    need += 1
                win[word1[l]] -= 1
                l += 1
            ans += l
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public long validSubstringCount(String word1, String word2) {
        if (word1.length() < word2.length()) {
            return 0;
        }
        int[] cnt = new int[26];
        int need = 0;
        for (int i = 0; i < word2.length(); ++i) {
            if (++cnt[word2.charAt(i) - 'a'] == 1) {
                ++need;
            }
        }
        long ans = 0;
        int[] win = new int[26];
        for (int l = 0, r = 0; r < word1.length(); ++r) {
            int c = word1.charAt(r) - 'a';
            if (++win[c] == cnt[c]) {
                --need;
            }
            while (need == 0) {
                c = word1.charAt(l) - 'a';
                if (win[c] == cnt[c]) {
                    ++need;
                }
                --win[c];
                ++l;
            }
            ans += l;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        if (word1.size() < word2.size()) {
            return 0;
        }
        int cnt[26]{};
        int need = 0;
        for (char& c : word2) {
            if (++cnt[c - 'a'] == 1) {
                ++need;
            }
        }
        long long ans = 0;
        int win[26]{};
        int l = 0;
        for (char& c : word1) {
            int i = c - 'a';
            if (++win[i] == cnt[i]) {
                --need;
            }
            while (need == 0) {
                i = word1[l] - 'a';
                if (win[i] == cnt[i]) {
                    ++need;
                }
                --win[i];
                ++l;
            }
            ans += l;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func validSubstringCount(word1 string, word2 string) (ans int64) {
    if len(word1) < len(word2) {
        return 0
    }
    cnt := [26]int{}
    need := 0
    for _, c := range word2 {
        cnt[c-'a']++
        if cnt[c-'a'] == 1 {
            need++
        }
    }
    win := [26]int{}
    l := 0
    for _, c := range word1 {
        i := int(c - 'a')
        win[i]++
        if win[i] == cnt[i] {
            need--
        }
        for need == 0 {
            i = int(word1[l] - 'a')
            if win[i] == cnt[i] {
                need++
            }
            win[i]--
            l++
        }
        ans += int64(l)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function validSubstringCount(word1: string, word2: string): number {
    if (word1.length < word2.length) {
        return 0;
    }
    const cnt: number[] = Array(26).fill(0);
    let need: number = 0;
    for (const c of word2) {
        if (++cnt[c.charCodeAt(0) - 97] === 1) {
            ++need;
        }
    }
    const win: number[] = Array(26).fill(0);
    let [ans, l] = [0, 0];
    for (const c of word1) {
        const i = c.charCodeAt(0) - 97;
        if (++win[i] === cnt[i]) {
            --need;
        }
        while (need === 0) {
            const j = word1[l].charCodeAt(0) - 97;
            if (win[j] === cnt[j]) {
                ++need;
            }
            --win[j];
            ++l;
        }
        ans += l;
    }
    return ans;
}

Comments