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^41 <= word2.length <= 10^4word1 and word2 consist only of lowercase English letters.
Hints for Count Substrings That Can Be Rearranged to Contain a String I
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.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.
Hint 3
Slide a window with a counter of how many letters are still "missing". Whenever the window
[left, right]is valid, alln - rightsubstrings starting atleftand ending atrightor later are valid; count them and movelefton.
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
- Fill
need[c]with the letter counts ofword2and setmissing = len(word2)— the number of letters still owed. - For each
right, takec = word1[right]: ifneed[c] > 0, decrementmissing; then decrementneed[c](it may go negative, meaning a surplus). - While
missing == 0: the window[left, right]is valid, so addn - right; then returnword1[left](increment itsneed, and if it becomes positive incrementmissing) and advanceleft. - 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
nin the worst case — use a 64-bit accumulator in fixed-width languages. - When
word2is longer thanword1, nothing is valid; the window never reachesmissing == 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 ansJava
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