Count Substrings That Can Be Rearranged to Contain a String II

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.

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

Solution

Method 1 – Sliding Window with Frequency Hashing (Linear Time)

Intuition

We want to count all substrings of word1 that can be rearranged to have word2 as a prefix. For this, the substring must have at least as many of each character as in word2. To achieve linear time, we use a sliding window of length len(word2) and a hash of the frequency difference between the window and word2.

Approach

1. Count the frequency of each character in word2 (let's call this need).
2. Use a sliding window of size len(word2) over word1 to maintain the frequency of characters in the current window.
3. For each window, if the window's frequency covers all characters in need, increment the answer.
4. For substrings longer than len(word2), extend the window and update the frequency, checking if the window still covers need.
5. Use a hash (tuple or string) of the difference between window and need to avoid recomputation and allow O(1) checks.
6. 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']++;
        vector<int> cnt(26, 0);
        long long ans = 0;
        int valid = 0;
        for (int i = 0; i < m && i < n; ++i) {
            cnt[word1[i] - 'a']++;
        }
        auto check = [&]() {
            for (int i = 0; i < 26; ++i) if (cnt[i] < need[i]) return false;
            return true;
        };
        if (n >= m && check()) ans++;
        for (int l = 1, r = m; r < n; ++l, ++r) {
            cnt[word1[l-1] - 'a']--;
            cnt[word1[r] - 'a']++;
            if (check()) 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']++
    }
    cnt := make([]int, 26)
    for i := 0; i < m && i < n; i++ {
        cnt[word1[i]-'a']++
    }
    var ans int64
    check := func() bool {
        for i := 0; i < 26; i++ {
            if cnt[i] < need[i] {
                return false
            }
        }
        return true
    }
    if n >= m && check() {
        ans++
    }
    for l, r := 1, m; r < n; l, r = l+1, r+1 {
        cnt[word1[l-1]-'a']--
        cnt[word1[r]-'a']++
        if check() {
            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']++;
        int[] cnt = new int[26];
        for (int i = 0; i < m && i < n; ++i) cnt[word1.charAt(i) - 'a']++;
        long ans = 0;
        boolean check() {
            for (int i = 0; i < 26; ++i) if (cnt[i] < need[i]) return false;
            return true;
        }
        if (n >= m && check()) ans++;
        for (int l = 1, r = m; r < n; ++l, ++r) {
            cnt[word1.charAt(l-1) - 'a']--;
            cnt[word1.charAt(r) - 'a']++;
            if (check()) 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']++
        val cnt = IntArray(26)
        for (i in 0 until minOf(m, n)) cnt[word1[i] - 'a']++
        var ans = 0L
        fun check(): Boolean {
            for (i in 0..25) if (cnt[i] < need[i]) return false
            return true
        }
        if (n >= m && check()) ans++
        var l = 1; var r = m
        while (r < n) {
            cnt[word1[l-1] - 'a']--
            cnt[word1[r] - 'a']++
            if (check()) ans++
            l++; r++
        }
        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
        cnt = [0] * 26
        for i in range(min(m, n)):
            cnt[ord(word1[i]) - ord('a')] += 1
        ans = 0
        def check():
            for i in range(26):
                if cnt[i] < need[i]:
                    return False
            return True
        if n >= m and check():
            ans += 1
        for l, r in zip(range(1, n-m+1), range(m, n)):
            cnt[ord(word1[l-1]) - ord('a')] -= 1
            cnt[ord(word1[r]) - ord('a')] += 1
            if check():
                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 cnt = vec![0; 26];
        for i in 0..std::cmp::min(m, n) {
            cnt[(word1[i] - b'a') as usize] += 1;
        }
        let mut ans = 0i64;
        let check = || (0..26).all(|i| cnt[i] >= need[i]);
        if n >= m && check() {
            ans += 1;
        }
        for l in 1..=n-m {
            let r = l + m - 1;
            cnt[(word1[l-1] - b'a') as usize] -= 1;
            cnt[(word1[r] - b'a') as usize] += 1;
            if check() {
                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]++;
        const cnt = Array(26).fill(0);
        for (let i = 0; i < Math.min(m, n); ++i) cnt[word1.charCodeAt(i) - 97]++;
        let ans = 0;
        function check() {
            for (let i = 0; i < 26; ++i) if (cnt[i] < need[i]) return false;
            return true;
        }
        if (n >= m && check()) ans++;
        for (let l = 1, r = m; r < n; ++l, ++r) {
            cnt[word1.charCodeAt(l-1) - 97]--;
            cnt[word1.charCodeAt(r) - 97]++;
            if (check()) ans++;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n * 26) which is linear for fixed alphabet size.
• 🧺 Space complexity: O(26) for the frequency arrays.