Count Substrings That Can Be Rearranged to Contain a String I

Medium
1367.

Count Substrings That Can Be Rearranged to Contain a String I

Count Substrings That Can Be Rearranged to Contain a String I is a medium coding problem on strings, hash table and sliding window, asked in Amazon and Google interviews.

You are given two strings word1 and word2 of lowercase English letters.

A string x is valid if its letters can be rearranged so that word2 is a prefix of the result — in other words, x contains every letter at least as many times as word2 does.

Return the number of valid non-empty substrings of word1. Substrings at different positions count separately even if they are equal.

CodeKairo note: the original allows word1 up to 10^5 letters and returns a 64-bit count; here word1.length <= 5 * 10^4, so the answer fits in a 32-bit integer.

Example 1

Input
word1 = "codekairo", word2 = "ok"
Output
13
Explanation
A valid substring must contain the `k` (index 4) and one of the two `o`s (index 1 or 8): 10 substrings start at index 0 or 1 and end at 4–8, and 3 more start at 2–4 and end at 8.

Example 2

Input
word1 = "abab", word2 = "ab"
Output
6
Explanation
All 10 substrings except the four single letters.

Example 3

Input
word1 = "aab", word2 = "abb"
Output
0
Explanation
`word1` has only one `b`.

Constraints

  • 1 <= word1.length <= 5 * 10^4
  • 1 <= word2.length <= 10^4
  • word1 and word2 consist only of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var validSubstringCount = function(word1, word2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Substrings That Can Be Rearranged to Contain a String I Solution

Count Substrings That Can Be Rearranged to Contain a String I solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Count Substrings That Can Be Rearranged to Contain a String I is a medium coding problem on strings, hash table and sliding window, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table, Sliding Window
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given two strings word1 and word2 of lowercase English letters.

A string x is valid if its letters can be rearranged so that word2 is a prefix of the result — in other words, x contains every letter at least as many times as word2 does.

Return the number of valid non-empty substrings of word1. Substrings at different positions count separately even if they are equal.

CodeKairo note: the original allows word1 up to 10^5 letters and returns a 64-bit count; here word1.length <= 5 * 10^4, so the answer fits in a 32-bit integer.

Example 1

Input: word1 = "codekairo", word2 = "ok"
Output: 13
Explanation: A valid substring must contain the `k` (index 4) and one of the two `o`s (index 1 or 8): 10 substrings start at index 0 or 1 and end at 4–8, and 3 more start at 2–4 and end at 8.

Example 2

Input: word1 = "abab", word2 = "ab"
Output: 6
Explanation: All 10 substrings except the four single letters.

Example 3

Input: word1 = "aab", word2 = "abb"
Output: 0
Explanation: `word1` has only one `b`.

Constraints

  • 1 <= word1.length <= 5 * 10^4
  • 1 <= word2.length <= 10^4
  • word1 and word2 consist only of lowercase English letters.

Hints for Count Substrings That Can Be Rearranged to Contain a String I

  1. Hint 1

    Order does not matter: a substring is valid exactly when, for every letter, its count is at least that letter's count in word2.

  2. Hint 2

    If a substring is valid, extending it to the right keeps it valid. So for each start there is a first end where it becomes valid, and every longer end works too.

  3. Hint 3

    Slide a window with a counter of how many letters are still "missing". Whenever the window [left, right] is valid, all n - right substrings starting at left and ending at right or later are valid; count them and move left on.

How to solve Count Substrings That Can Be Rearranged to Contain a String I

Validity only compares letter counts against word2's, and it is monotone: supersets of a valid substring are valid. For each start, find the shortest valid end with a sliding window and count all its extensions at once.

Approach

  1. Fill need[c] with the letter counts of word2 and set missing = len(word2) — the number of letters still owed.
  2. For each right, take c = word1[right]: if need[c] > 0, decrement missing; then decrement need[c] (it may go negative, meaning a surplus).
  3. While missing == 0: the window [left, right] is valid, so add n - right; then return word1[left] (increment its need, and if it becomes positive increment missing) and advance left.
  4. Return the total.

Why it works

missing is exactly how many letters of word2 the window still lacks, counted with multiplicity, so the window is valid precisely when it is 0. For each start left, the first right at which the window becomes valid is found by this loop, and because extensions stay valid, the substrings [left, right..n-1] are exactly the valid ones starting at left — n - right of them. Both pointers only move forward.

Complexity

  • Time — O(n + m)
  • Space — O(26)

Pitfalls

  • Count every valid end for a start, not just the shortest one.
  • The answer is quadratic in n in the worst case — use a 64-bit accumulator in fixed-width languages.
  • When word2 is longer than word1, nothing is valid; the window never reaches missing == 0.

Reference solution

Python

def validSubstringCount(word1: str, word2: str) -> int:
    need = [0] * 26
    for ch in word2:
        need[ord(ch) - 97] += 1
    missing = len(word2)
    n = len(word1)
    left = 0
    ans = 0
    for right in range(n):
        c = ord(word1[right]) - 97
        if need[c] > 0:
            missing -= 1
        need[c] -= 1
        while missing == 0:
            ans += n - right
            d = ord(word1[left]) - 97
            need[d] += 1
            if need[d] > 0:
                missing += 1
            left += 1
    return ans

Java

public static int validSubstringCount(String word1, String word2) {
    int[] need = new int[26];
    for (int i = 0; i < word2.length(); i++) need[word2.charAt(i) - 'a']++;
    int missing = word2.length(), n = word1.length(), left = 0;
    long ans = 0;
    for (int right = 0; right < n; right++) {
        int c = word1.charAt(right) - 'a';
        if (need[c] > 0) missing--;
        need[c]--;
        while (missing == 0) {
            ans += n - right;
            int d = word1.charAt(left) - 'a';
            need[d]++;
            if (need[d] > 0) missing++;
            left++;
        }
    }
    return (int) ans;
}

C++

int validSubstringCount(string word1, string word2) {
    int need[26] = {0};
    for (char ch : word2) need[ch - 'a']++;
    int missing = word2.size(), n = word1.size(), left = 0;
    long long ans = 0;
    for (int right = 0; right < n; right++) {
        int c = word1[right] - 'a';
        if (need[c] > 0) missing--;
        need[c]--;
        while (missing == 0) {
            ans += n - right;
            int d = word1[left] - 'a';
            need[d]++;
            if (need[d] > 0) missing++;
            left++;
        }
    }
    return (int) ans;
}

JavaScript

var validSubstringCount = function(word1, word2) {
    var need = new Array(26).fill(0);
    for (var i = 0; i < word2.length; i++) need[word2.charCodeAt(i) - 97]++;
    var missing = word2.length, n = word1.length, left = 0, ans = 0;
    for (var right = 0; right < n; right++) {
        var c = word1.charCodeAt(right) - 97;
        if (need[c] > 0) missing--;
        need[c]--;
        while (missing === 0) {
            ans += n - right;
            var d = word1.charCodeAt(left) - 97;
            need[d]++;
            if (need[d] > 0) missing++;
            left++;
        }
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets