3297. Count Substrings That Can Be Rearranged to Contain a String I

[DrDread746]

Problem Number

3297

Problem Title

Count Substrings That Can Be Rearranged to Contain a String I

LeetCode Link

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

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

Character Frequency Setup:
Create two frequency arrays: one for word2 (map2) and one for the current window in word1 (map1).

Sliding Window:
Expand the right pointer r step by step, updating map1.
If a character’s frequency in map1 matches that in map2, increase a count that tracks how many required characters are currently satisfied.

Valid Window Check:
When all required characters are satisfied (count == word2.length()), the window is valid.
Every substring starting from l to the end of word1 with this configuration will also be valid, so we add (word1.length() - r) to the answer.

Shrink Window:
Move the left pointer l to make the window smaller, adjusting counts accordingly.
If reducing a character makes its frequency fall below the requirement, reduce count.

Continue Until Done:
Repeat until the right pointer reaches the end of word1.

Intuition

The goal is to count all substrings of word1 that contain at least as many occurrences of each character as in word2.
To do this efficiently, we can use a sliding window technique. As we expand the window, we keep track of character frequencies. Once the current window satisfies the frequency requirement for all characters in word2, every substring starting from the current left pointer up to the end of the string is valid ; so we can directly count them instead of checking each one individually.

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