3298. Count Substrings That Can Be Rearranged to Contain a String II

[DrDread746]

Problem Number

3298

Problem Title

Count Substrings That Can Be Rearranged to Contain a String II

LeetCode Link

https://leetcode.com/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii/

Contribution Checklist

• I have written the Approach section.
• I have written the Intuition section.
• I have included a working C++ solution.
• I will raise a PR and ensure the filename follows the convention [Number]. [Problem Title].cpp.

Approach

Initialize Frequency Maps:
Use two arrays map1 and map2 of size 26 (or 27 for safety) to store the frequency of each character.
map2 stores frequencies from word2.

Sliding Window Expansion:
Move the right pointer r through word1, updating map1.
If the frequency of a character in map1 becomes equal to that in map2, increase count — meaning this character’s requirement is satisfied.

Valid Window Detection:
When count == word2.length(), the current window contains all the characters required by word2.
All substrings starting from this left index l to the end of word1 are valid, so add (word1.length() - r) to the result.

Shrink the Window:
Move the left pointer l and update the frequency of the character being removed.
If removing it breaks the requirement, decrease count.

Repeat Until Done:
Continue expanding and shrinking the window until r reaches the end of word1.

Intuition

The problem asks us to count how many substrings of word1 contain at least as many occurrences of each character as in word2.
Instead of checking every possible substring (which would be very slow), we can use a sliding window approach to efficiently keep track of character frequencies.

The idea is to expand a window using a right pointer until it contains all the required characters of word2. Once that happens, all longer substrings extending to the right will also be valid. So, we can directly count all of them in one step. Then, we move the left pointer to look for the next valid window.

Solution in C++

class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        int count = 0;
        long long ans = 0;
        int l = 0, r = 0;
        vector<int> map2(27, 0), map1(27, 0);
        for (int i = 0; i < word2.size(); i++) {
            map2[word2[i] - 'a']++;
        }
        while (r < word1.size()) {
            map1[word1[r] - 'a']++;
            if (map1[word1[r] - 'a'] == map2[word1[r] - 'a'])
                count += map2[word1[r] - 'a'];
            while (count == word2.size()) {
                ans += (word1.size() - r);
                map1[word1[l] - 'a']--;
                if (map1[word1[l] - 'a'] < map2[word1[l] - 'a'])
                    count -= map2[word1[l] - 'a'];
                l++;
            }
            r++;
        }
        return ans;
    }
};