Code : Count Substrings That Can Be Rearranged to Contain a String II

class Solution {
  public:
    long long validSubstringCount(string word1, string word2);
};

long long Solution ::validSubstringCount(string word1, string word2) {
    int n = word1.length();
    vector<int> need(26, 0);
    for (char ch : word2) {
        need[ch - 'a']++;
    }

    vector<vector<int>> freq(26, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        freq[word1[i] - 'a'][i] = 1;
    }
    for (int c = 0; c < 26; c++) {
        auto &pref = freq[c];
        for (int i = 1; i < n; i++) {
            pref[i] += pref[i - 1];
        }
    }

    auto query_sum = [&](int c, int l, int r) {
        auto &pref = freq[c];
        return pref[r] - (l ? pref[l - 1] : 0);
    };

    auto is_good = [&](int low, int high) {
        for (int c = 0; c < 26; c++) {
            if (query_sum(c, low, high) < need[c]) {
                return false;
            }
        }
        return true;
    };

    // dp[i] is the number of good substrings starting at index i.
    vector<int> dp(n);
    for (int i = 0; i < n; i++) {
        int low = i, high = n - 1, res = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (is_good(i, mid)) {
                res = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        // res is now pointing at the smallest good index.
        if (res != -1) {
            dp[i] = n - res;
        }
    }

    return accumulate(dp.begin(), dp.end(), 0LL);
}

class Solution {
  public:
    long long validSubstringCount(string word1, string word2);
};

long long Solution ::validSubstringCount(string word1, string word2) {
    int n = word1.length();
    vector<int> need(26, 0);
    for (char ch : word2) {
        need[ch - 'a']++;
    }

    vector<vector<int>> freq(26, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        freq[word1[i] - 'a'][i] = 1;
    }
    for (int c = 0; c < 26; c++) {
        auto &pref = freq[c];
        for (int i = 1; i < n; i++) {
            pref[i] += pref[i - 1];
        }
    }

    auto query_sum = [&](int c, int l, int r) {
        auto &pref = freq[c];
        return pref[r] - (l ? pref[l - 1] : 0);
    };

    auto is_good = [&](int low, int high) {
        for (int c = 0; c < 26; c++) {
            if (query_sum(c, low, high) < need[c]) {
                return false;
            }
        }
        return true;
    };

    // dp[i] is the number of good substrings starting at index i.
    vector<int> dp(n);
    int j = 0; // j points to the first good index.
    for (int i = 0; i < n; i++) {
        while (j < n && !is_good(i, j)) {
            j++;
        }
        dp[i] = n - j;
    }

    return accumulate(dp.begin(), dp.end(), 0LL);
}

class Solution {
  public:
    long long validSubstringCount(string word1, string word2);
};

long long Solution ::validSubstringCount(string word1, string word2) {
    int n = word1.length();
    vector<int> need(26, 0);
    for (char ch : word2) {
        need[ch - 'a']++;
    }

    int bad = 0;
    for (int c = 0; c < 26; c++) {
        bad += (need[c] > 0);
    }
    vector<int> have(26, 0);

    // dp[i] is the number of good substrings starting at index i.
    vector<int> dp(n);
    int j = -1; // j points to the first good index.
    for (int i = 0; i < n; i++) {
        while (j < n && bad) {
            j++;
            if (j == n) {
                break;
            }
            int c = word1[j] - 'a';
            // Add j.
            have[c]++;
            if (have[c] == need[c]) {
                bad--;
            }
        }
        dp[i] = n - j;
        // Remove i.
        int c = word1[i] - 'a';
        have[c]--;
        if (have[c] == need[c] - 1) {
            bad++;
        }
    }

    return accumulate(dp.begin(), dp.end(), 0LL);
}