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

Problem link

tags: leedcode hard python c++ Sliding Window

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.

Solution 1 - Sliding Window

C++

class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        vector<int> cnt(26, 0);
        for (char& c: word2) {
            cnt[c - 'a']++;
        }
        int alphaCnt = 0;
        for (int& c: cnt) {
            alphaCnt += c > 0;
        }

        int l = 0;
        long long ans = 0;
        for (int r = 0; r < word1.size(); r++) {
            cnt[word1[r] - 'a']--;
            alphaCnt -= cnt[word1[r] - 'a'] == 0;
            while (alphaCnt == 0) {
                cnt[word1[l] - 'a']++;
                alphaCnt += cnt[word1[l] - 'a'] == 1;
                l++;
            }
            ans += l;
        }
        return ans;
    }
};

Complexity

	Time Complexity	Space Complexity
Solution 1	O(n)	O(1)

Note

跟LC. 3297一樣