# Count Substrings That Can Be Rearranged to Contain a String II
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii)
Canonical: https://scaleengineer.com/dsa/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii
**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`.

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

# Approaches
## Brute Force Iteration
This method involves checking every possible substring of `word1`. For each substring, we determine if it's "valid" by comparing its character counts with the character counts of `word2`. A substring is valid if it contains at least as many of each character as `word2` does.
**Time:** O(N^2 * A), where N is the length of `word1` and A is the alphabet size (26). The nested loops run in O(N^2) and the frequency comparison inside takes O(A). · **Space:** O(A), where A is the alphabet size (26). This is for storing the frequency maps.
**Pros:** Simple to conceptualize and implement.; Correct for smaller inputs.
**Cons:** Highly inefficient due to its quadratic time complexity.; Will result in a 'Time Limit Exceeded' error for the input sizes specified in the problem constraints.
### Explanation
First, we pre-calculate the character frequency map of `word2`. This map, let's call it `targetFreq`, will be used as the reference for our validity checks.

We then use two nested loops to generate all substrings of `word1`. The outer loop selects the starting index `i`, and the inner loop selects the ending index `j`.

For each starting index `i`, we initialize a `currentFreq` map for the characters. As the inner loop progresses from `j = i` to the end of the string, we incrementally build the substring and update `currentFreq`.

At each step `j`, we have the frequency map for the substring `word1[i..j]`. We then check if this substring is valid by comparing `currentFreq` with `targetFreq`. If the substring is valid, we increment a total counter. After checking all substrings, the total counter gives the final answer.

```java
class Solution {
    public long countSubstrings(String word1, String word2) {
        int[] targetFreq = new int[26];
        for (char c : word2.toCharArray()) {
            targetFreq[c - 'a']++;
        }

        long validCount = 0;
        int n = word1.length();

        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, targetFreq)) {
                    // If word1[i..j] is valid, all substrings word1[i..k] where k > j are also valid.
                    // We can optimize by adding (n - j) and breaking the inner loop.
                    // But for a basic brute force, we check each one.
                    validCount++;
                }
            }
        }
        return validCount;
    }

    private boolean isSufficient(int[] currentFreq, int[] targetFreq) {
        for (int k = 0; k < 26; k++) {
            if (currentFreq[k] < targetFreq[k]) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Create a frequency map `targetFreq` for `word2`.
- Initialize `count = 0`.
- Loop `i` from `0` to `word1.length() - 1`:
  - Create an empty frequency map `currentFreq`.
  - Loop `j` from `i` to `word1.length() - 1`:
    - Add `word1.charAt(j)` to `currentFreq`.
    - Check if `currentFreq` is sufficient compared to `targetFreq` by iterating through all 26 characters.
    - If it is, increment `count`.
- Return `count`.

## Optimal Sliding Window
A much more efficient approach uses the sliding window technique. The core idea is that if a substring `word1[i..j]` is valid, then any longer substring starting at `i` (e.g., `word1[i..j+1]`) is also valid. This property allows us to avoid re-checking every single substring. We can find the *first* valid substring starting at `i` and then quickly count all subsequent valid ones.
**Time:** O(N + M), where N is `word1.length()` and M is `word2.length()`. `M` for pre-calculation, and `N` because both pointers `i` and `j` traverse `word1` only once. · **Space:** O(A), where A is the alphabet size (26). This is for the frequency maps, which is constant space.
**Pros:** Optimal time complexity (linear), as required by the problem.; Efficient memory usage (constant space).; Guaranteed to pass within the given time and memory constraints.
**Cons:** The logic is more complex than the brute-force approach and requires careful implementation to handle window expansion and shrinking correctly.
### Explanation
We use two pointers, `i` (left) and `j` (right), to define a "window" on `word1`. The pointer `i` iterates from the beginning to the end of `word1`, representing the start of our potential substrings.

For each `i`, we expand the window by advancing `j` until the substring `word1[i..j]` becomes valid. To efficiently track validity, we maintain a count of "deficient" character types. Initially, this is the number of unique characters in `word2`. As we expand the window by including `word1.charAt(j)`, we update our window's frequency map. If the count for a character `c` in our window matches the required count from `word2`, we decrement the deficient count.

Once the deficient count drops to zero, we have found the shortest valid substring starting at `i`. Let's say it ends at index `j-1`. Then we know that all substrings starting at `i` and ending at any index from `j-1` to `N-1` (where `N` is `word1.length()`) are also valid. The number of such substrings is `N - (j-1)`. We add this to our total count.

We then slide the window forward by incrementing `i`. This involves removing `word1.charAt(i)` from our window's frequency map and updating the deficient count if this removal makes a previously satisfied character deficient again. The right pointer `j` does not reset, ensuring that each character in `word1` is visited at most twice.

```java
class Solution {
    public long countSubstrings(String word1, String word2) {
        int n = word1.length();
        int[] targetFreq = new int[26];
        for (char c : word2.toCharArray()) {
            targetFreq[c - 'a']++;
        }

        int mismatches = 0;
        for (int count : targetFreq) {
            if (count > 0) {
                mismatches++;
            }
        }

        long totalCount = 0;
        int[] currentFreq = new int[26];
        int i = 0, j = 0;

        for (i = 0; i < n; i++) {
            // Expand window by moving right pointer j
            while (j < n && mismatches > 0) {
                char charJ = word1.charAt(j);
                currentFreq[charJ - 'a']++;
                if (currentFreq[charJ - 'a'] == targetFreq[charJ - 'a']) {
                    mismatches--;
                }
                j++;
            }

            // If window is valid, count all substrings starting at i
            if (mismatches == 0) {
                totalCount += (long)n - j + 1;
            }

            // Shrink window from the left by moving pointer i
            char charI = word1.charAt(i);
            if (targetFreq[charI - 'a'] > 0 && currentFreq[charI - 'a'] == targetFreq[charI - 'a']) {
                mismatches++;
            }
            currentFreq[charI - 'a']--;
        }

        return totalCount;
    }
}
```
### Algorithm
- Pre-calculate `targetFreq` for `word2` and count the number of unique characters in it, let's call this `mismatches`.
- Initialize `totalCount = 0`, left pointer `i = 0`, right pointer `j = 0`, and an empty `currentFreq` map.
- Loop `i` from `0` to `word1.length() - 1`:
  - While `j < word1.length()` and `mismatches > 0`:
    - Add `word1.charAt(j)` to `currentFreq`.
    - If `currentFreq` for this character now matches `targetFreq`, decrement `mismatches`.
    - Increment `j`.
  - If `mismatches == 0`, it means `word1[i..j-1]` is the first valid substring starting at `i`. All substrings starting at `i` and ending at `j-1` or later are also valid. Add `word1.length() - (j - 1)` to `totalCount`.
  - Shrink the window from the left: Remove `word1.charAt(i)` from `currentFreq`.
  - If `currentFreq` for this character was exactly matching `targetFreq` before removal, it becomes deficient, so increment `mismatches`.
- Return `totalCount`.

# 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

```