Count Substrings That Can Be Rearranged to Contain a String I

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.

Examples

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^5
• 1 <= word2.length <= 10^4
• word1 and word2 consist only of lowercase English letters.

Solution

Method 1 – Sliding Window with Frequency Counting

Intuition

To check if a substring of word1 can be rearranged to have word2 as a prefix, the substring must have at least as many of each character as in word2. We can use a sliding window of length at least len(word2) and count frequencies to check this efficiently.

Approach

1. Count the frequency of each character in word2 (let's call this need).
2. For each possible substring of word1 of length at least len(word2), use a sliding window to maintain the frequency of characters in the current window.
3. For each window, check if the window's frequency covers all characters in need (i.e., for every character, window count >= need count).
4. If so, increment the answer.
5. Return the total count.

Code

C++

class Solution {
public:
    long long countValidSubstrings(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<int> need(26, 0);
        for (char c : word2) need[c - 'a']++;
        long long ans = 0;
        for (int l = 0; l <= n - m; ++l) {
            vector<int> cnt(26, 0);
            for (int r = l; r < n; ++r) {
                cnt[word1[r] - 'a']++;
                if (r - l + 1 >= m) {
                    bool ok = true;
                    for (int i = 0; i < 26; ++i) {
                        if (cnt[i] < need[i]) { ok = false; break; }
                    }
                    if (ok) ans++;
                }
            }
        }
        return ans;
    }
};

Go

type Solution struct{}
func (Solution) CountValidSubstrings(word1, word2 string) int64 {
    n, m := len(word1), len(word2)
    need := make([]int, 26)
    for i := 0; i < m; i++ {
        need[word2[i]-'a']++
    }
    var ans int64
    for l := 0; l <= n-m; l++ {
        cnt := make([]int, 26)
        for r := l; r < n; r++ {
            cnt[word1[r]-'a']++
            if r-l+1 >= m {
                ok := true
                for i := 0; i < 26; i++ {
                    if cnt[i] < need[i] {
                        ok = false
                        break
                    }
                }
                if ok {
                    ans++
                }
            }
        }
    }
    return ans
}

Java

class Solution {
    public long countValidSubstrings(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[] need = new int[26];
        for (char c : word2.toCharArray()) need[c - 'a']++;
        long ans = 0;
        for (int l = 0; l <= n - m; ++l) {
            int[] cnt = new int[26];
            for (int r = l; r < n; ++r) {
                cnt[word1.charAt(r) - 'a']++;
                if (r - l + 1 >= m) {
                    boolean ok = true;
                    for (int i = 0; i < 26; ++i) {
                        if (cnt[i] < need[i]) { ok = false; break; }
                    }
                    if (ok) ans++;
                }
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun countValidSubstrings(word1: String, word2: String): Long {
        val n = word1.length
        val m = word2.length
        val need = IntArray(26)
        for (c in word2) need[c - 'a']++
        var ans = 0L
        for (l in 0..n-m) {
            val cnt = IntArray(26)
            for (r in l until n) {
                cnt[word1[r] - 'a']++
                if (r - l + 1 >= m) {
                    var ok = true
                    for (i in 0..25) {
                        if (cnt[i] < need[i]) { ok = false; break }
                    }
                    if (ok) ans++
                }
            }
        }
        return ans
    }
}

Python

class Solution:
    def countValidSubstrings(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        need = [0] * 26
        for c in word2:
            need[ord(c) - ord('a')] += 1
        ans = 0
        for l in range(n - m + 1):
            cnt = [0] * 26
            for r in range(l, n):
                cnt[ord(word1[r]) - ord('a')] += 1
                if r - l + 1 >= m:
                    if all(cnt[i] >= need[i] for i in range(26)):
                        ans += 1
        return ans

Rust

impl Solution {
    pub fn count_valid_substrings(word1: String, word2: String) -> i64 {
        let n = word1.len();
        let m = word2.len();
        let word1 = word1.as_bytes();
        let word2 = word2.as_bytes();
        let mut need = vec![0; 26];
        for &c in word2.iter() {
            need[(c - b'a') as usize] += 1;
        }
        let mut ans = 0i64;
        for l in 0..=n-m {
            let mut cnt = vec![0; 26];
            for r in l..n {
                cnt[(word1[r] - b'a') as usize] += 1;
                if r - l + 1 >= m {
                    if (0..26).all(|i| cnt[i] >= need[i]) {
                        ans += 1;
                    }
                }
            }
        }
        ans
    }
}

TypeScript

class Solution {
    countValidSubstrings(word1: string, word2: string): number {
        const n = word1.length, m = word2.length;
        const need = Array(26).fill(0);
        for (const c of word2) need[c.charCodeAt(0) - 97]++;
        let ans = 0;
        for (let l = 0; l <= n - m; ++l) {
            const cnt = Array(26).fill(0);
            for (let r = l; r < n; ++r) {
                cnt[word1.charCodeAt(r) - 97]++;
                if (r - l + 1 >= m) {
                    if (need.every((v, i) => cnt[i] >= v)) ans++;
                }
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n^2 * 26) in the worst case, where n is the length of word1.
• 🧺 Space complexity: O(26) for the frequency arrays.