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

### [Problem link](https://leetcode.com/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-i/)

###### tags: `leedcode` `medium` `c++` `Sliding Window`

You are given two strings <code>word1</code> and <code>word2</code>.

A string <code>x</code> is called **valid** if <code>x</code> can be rearranged to have <code>word2</code> as a <span data-keyword="string-prefix">prefix.

Return the total number of **valid** <span data-keyword="substring-nonempty">substrings of <code>word1</code>.

**Example 1:**

<div class="example-block">
Input: <span class="example-io">word1 = "bcca", word2 = "abc"

Output: <span class="example-io">1

Explanation:

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

**Example 2:**

<div class="example-block">
Input: <span class="example-io">word1 = "abcabc", word2 = "abc"

Output: <span class="example-io">10

Explanation:

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

**Example 3:**

<div class="example-block">
Input: <span class="example-io">word1 = "abcabc", word2 = "aaabc"

Output: <span class="example-io">0

**Constraints:**

- <code>1 <= word1.length <= 10⁵</code>
- <code>1 <= word2.length <= 10⁴</code>
- <code>word1</code> and <code>word2</code> consist only of lowercase English letters.

## Solution 1 - Sliding Window
#### C++

class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        vector<int> cnt(26, 0);
        for (char& c: word2) {
            cnt[c - 'a']++;
        }
        int alphaCnt = 0;
        for (int& c: cnt) {
            alphaCnt += c > 0;
        }

        int l = 0;
        long long ans = 0;
        for (int r = 0; r < word1.size(); r++) {
            cnt[word1[r] - 'a']--;
            alphaCnt -= cnt[word1[r] - 'a'] == 0;
            while (alphaCnt == 0) {
                cnt[word1[l] - 'a']++;
                alphaCnt += cnt[word1[l] - 'a'] == 1;
                l++;
            }
            ans += l;
        }
        return ans;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |

## Note
Sol1:
如果l = 4, r = 6 是可以重構的最小長度，則
l = 3, r = 6
l = 2, r = 6
l = 1, r = 6
l = 0, r = 6
都可以是答案，所以ans += l