# Count Substrings That Can Be Rearranged to Contain a String I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-i)
Canonical: https://scaleengineer.com/dsa/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-i
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Hash Table, String
---
## Problem
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.

# Approaches
## Brute Force by Checking All Substrings
This approach involves iterating through every possible substring of `word1`. For each substring, we calculate its character frequency and check if it meets the criteria to be a "valid" string. A substring is considered valid if its character counts are greater than or equal to the character counts of `word2` for every character in the alphabet. While straightforward, this method is computationally expensive.
**Time:** O(N^2 * C), where N is the length of `word1` and C is the size of the character set (26). The two nested loops iterate through all O(N^2) substrings, and for each, the check takes O(C) time. · **Space:** O(C), where C is the size of the character set (26). This space is used to store the frequency maps.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs.
**Cons:** This approach is too slow for the given constraints (`word1.length` up to 10^5), as an O(N^2) complexity will lead to a 'Time Limit Exceeded' error.
### Explanation
The brute-force method systematically checks every substring. We can optimize the process slightly by not re-calculating the frequency map for each substring from scratch. For a fixed starting point `i`, as we extend the substring by incrementing the end point `j`, we can update the frequency map of the current substring in O(1) time. Then, for each new substring `word1[i...j]`, we perform a check against the frequency map of `word2`.

```java
class Solution {
    public long countSubstrings(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        long count = 0;

        int[] freq2 = new int[26];
        for (char c : word2.toCharArray()) {
            freq2[c - 'a']++;
        }

        for (int i = 0; i < n; i++) {
            int[] currentFreq = new int[26];
            for (int j = i; j < n; j++) {
                currentFreq[word1.charAt(j) - 'a']++;
                if (isSufficient(currentFreq, freq2)) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isSufficient(int[] freq1, int[] freq2) {
        for (int i = 0; i < 26; i++) {
            if (freq1[i] < freq2[i]) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Pre-calculate the character frequency map of `word2`, let's call it `freq2`.
- Initialize a counter for valid substrings, `count`, to 0.
- Use nested loops to generate all substrings of `word1`. The outer loop iterates through the starting index `i` from `0` to `n-1`, and the inner loop iterates through the ending index `j` from `i` to `n-1`.
- For each substring `word1[i...j]`, maintain a running character frequency map, `currentFreq`.
- After adding `word1.charAt(j)` to the window, check if `currentFreq` has at least as many of each character as `freq2`.
- If the condition is met, it means the substring `word1[i...j]` is valid, so increment the `count`.
- After iterating through all substrings, return the total `count`.

## Optimal Sliding Window Approach
A more efficient solution uses the sliding window technique. The core idea relies on a key property: if a substring `word1[i...j]` is valid, then any longer substring starting at the same position `i` (e.g., `word1[i...k]` where `k > j`) must also be valid. This monotonicity allows us to avoid re-checking many substrings. We can find the smallest valid substring starting at each position `i` and then quickly calculate how many valid substrings start at that position.
**Time:** O(N + M), where N is the length of `word1` and M is the length of `word2`. The `left` and `right` pointers each traverse `word1` at most once, leading to O(N) time for the main loop. Calculating the frequency map for `word2` takes O(M) time. · **Space:** O(C), where C is the size of the character set (26). This constant space is used for the frequency maps.
**Pros:** Highly efficient with linear time complexity.; Optimal solution for the given constraints.
**Cons:** The logic is more complex to reason about compared to the brute-force approach.
### Explanation
We use two pointers, `left` and `right`, to maintain a window over `word1`. The `left` pointer iterates through all possible starting positions of a substring. For each `left`, we expand the window by moving `right` forward until the substring `word1[left...right-1]` contains enough characters to satisfy the requirements of `word2`. Once this minimal valid window is found, we know that this window, and any window starting at `left` that extends beyond `right-1`, are all valid. The number of such valid substrings is `n - (right - 1)`. We add this to our total count. Then, we slide the window forward by incrementing `left` and removing `word1.charAt(left)` from our window's frequency count. The `right` pointer continues from where it was, ensuring that each character in `word1` is visited by `left` and `right` at most once.

```java
class Solution {
    public long countSubstrings(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        long count = 0;

        int[] freq2 = new int[26];
        for (char c : word2.toCharArray()) {
            freq2[c - 'a']++;
        }

        int[] windowFreq = new int[26];
        int right = 0;
        for (int left = 0; left < n; left++) {
            // Expand the window by moving 'right' until the substring is valid
            while (right < n && !isSufficient(windowFreq, freq2)) {
                windowFreq[word1.charAt(right) - 'a']++;
                right++;
            }

            // If the window is valid, all substrings starting at 'left' and ending at 'right-1' or later are valid.
            if (isSufficient(windowFreq, freq2)) {
                count += (long)n - (right - 1);
            }

            // Shrink the window from the left for the next iteration
            windowFreq[word1.charAt(left) - 'a']--;
        }
        return count;
    }

    private boolean isSufficient(int[] freq1, int[] freq2) {
        for (int i = 0; i < 26; i++) {
            if (freq1[i] < freq2[i]) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- First, compute the character frequency map for `word2`, let's call it `freq2`.
- Initialize two pointers, `left = 0` and `right = 0`, to represent the current window `word1[left...right-1]`.
- Initialize a frequency map for the window, `windowFreq`, and a total count of valid substrings, `count = 0`.
- Iterate with the `left` pointer from `0` to `n-1`.
- For each `left`, expand the window by advancing the `right` pointer until the window `word1[left...right-1]` becomes valid (i.e., its character counts are sufficient).
- Once a valid window `word1[left...right-1]` is found, we know that any substring starting at `left` and ending at `right-1` or later is also valid. The number of such substrings is `n - (right - 1)`. Add this to `count`.
- After processing `left`, shrink the window by decrementing the count of `word1.charAt(left)` and advancing `left` to the next position.
- The `right` pointer does not reset, which is key to the algorithm's efficiency.
- Return the total `count`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```