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

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

Tag: Two Pointer

typedef long long ll;
class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        int n = word1.size();
        vector<int> cnt(26, 0);
        int need = 0;
        for (auto &x: word2) {
            cnt[x - 'a'] += 1;
            if (cnt[x - 'a'] == 1) need += 1;
        }
        vector<int> cur(26, 0);
        ll ans = 0;
        int l = 0, r = 0;
        while (r < n) {
            while (r < n && need) {
                cur[word1[r] - 'a'] += 1;
                if (cur[word1[r] - 'a'] == cnt[word1[r] - 'a']) need -= 1;
                r += 1;
            }
            while (need == 0) {
                ans += n - r + 1;
                cur[word1[l] - 'a'] -= 1;
                if (cur[word1[l] - 'a'] == (cnt[word1[l] - 'a'] - 1)) need += 1;
                l += 1;
            }
        }
        return ans;
    }
};

Time Complexity: O(n)
Space: O(26)

算是挺基本的左加加右減減類型的題目