Welcome to Subscribe On Youtube
3298. Count Substrings That Can Be Rearranged to Contain a String II
Description
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 <= 1061 <= word2.length <= 104word1andword2consist only of lowercase English letters.
Solutions
Solution 1: Sliding Window
The problem is essentially to find how many substrings in $\textit{word1}$ contain all the characters in $\textit{word2}$. We can use a sliding window to handle this.
First, if the length of $\textit{word1}$ is less than the length of $\textit{word2}$, then it is impossible for $\textit{word1}$ to contain all the characters of $\textit{word2}$, so we directly return $0$.
Next, we use a hash table or an array of length $26$ called $\textit{cnt}$ to count the occurrences of characters in $\textit{word2}$. Then, we use $\textit{need}$ to record how many more characters are needed to meet the condition, initialized to the length of $\textit{cnt}$.
We then use a sliding window $\textit{win}$ to record the occurrences of characters in the current window. We use $\textit{ans}$ to record the number of substrings that meet the condition, and $\textit{l}$ to record the left boundary of the window.
We traverse each character in $\textit{word1}$. For the current character $c$, we add it to $\textit{win}$. If the value of $\textit{win}[c]$ equals $\textit{cnt}[c]$, it means the current window already contains one of the characters in $\textit{word2}$, so we decrement $\textit{need}$ by one. If $\textit{need}$ equals $0$, it means the current window contains all the characters in $\textit{word2}$. We need to shrink the left boundary of the window until $\textit{need}$ is greater than $0$. Specifically, if $\textit{win}[\textit{word1}[l]]$ equals $\textit{cnt}[\textit{word1}[l]]$, it means the current window contains one of the characters in $\textit{word2}$. After shrinking the left boundary, it no longer meets the condition, so we increment $\textit{need}$ by one and decrement $\textit{win}[\textit{word1}[l]]$ by one. Then, we increment $\textit{l}$ by one. At this point, the window is $[l, r]$. For any $0 \leq l’ < l$, $[l’, r]$ are substrings that meet the condition, and there are $l$ such substrings, which we add to the answer.
After traversing all characters in $\textit{word1}$, we get the answer.
The time complexity is $O(n + m)$, where $n$ and $m$ are the lengths of $\textit{word1}$ and $\textit{word2}$, respectively. The space complexity is $O(|\Sigma|)$, where $\Sigma$ is the character set. Here, it is the set of lowercase letters, so the space complexity is constant.
-
class Solution { public long validSubstringCount(String word1, String word2) { if (word1.length() < word2.length()) { return 0; } int[] cnt = new int[26]; int need = 0; for (int i = 0; i < word2.length(); ++i) { if (++cnt[word2.charAt(i) - 'a'] == 1) { ++need; } } long ans = 0; int[] win = new int[26]; for (int l = 0, r = 0; r < word1.length(); ++r) { int c = word1.charAt(r) - 'a'; if (++win[c] == cnt[c]) { --need; } while (need == 0) { c = word1.charAt(l) - 'a'; if (win[c] == cnt[c]) { ++need; } --win[c]; ++l; } ans += l; } return ans; } } -
class Solution { public: long long validSubstringCount(string word1, string word2) { if (word1.size() < word2.size()) { return 0; } int cnt[26]{}; int need = 0; for (char& c : word2) { if (++cnt[c - 'a'] == 1) { ++need; } } long long ans = 0; int win[26]{}; int l = 0; for (char& c : word1) { int i = c - 'a'; if (++win[i] == cnt[i]) { --need; } while (need == 0) { i = word1[l] - 'a'; if (win[i] == cnt[i]) { ++need; } --win[i]; ++l; } ans += l; } return ans; } }; -
class Solution: def validSubstringCount(self, word1: str, word2: str) -> int: if len(word1) < len(word2): return 0 cnt = Counter(word2) need = len(cnt) ans = l = 0 win = Counter() for c in word1: win[c] += 1 if win[c] == cnt[c]: need -= 1 while need == 0: if win[word1[l]] == cnt[word1[l]]: need += 1 win[word1[l]] -= 1 l += 1 ans += l return ans -
func validSubstringCount(word1 string, word2 string) (ans int64) { if len(word1) < len(word2) { return 0 } cnt := [26]int{} need := 0 for _, c := range word2 { cnt[c-'a']++ if cnt[c-'a'] == 1 { need++ } } win := [26]int{} l := 0 for _, c := range word1 { i := int(c - 'a') win[i]++ if win[i] == cnt[i] { need-- } for need == 0 { i = int(word1[l] - 'a') if win[i] == cnt[i] { need++ } win[i]-- l++ } ans += int64(l) } return } -
function validSubstringCount(word1: string, word2: string): number { if (word1.length < word2.length) { return 0; } const cnt: number[] = Array(26).fill(0); let need: number = 0; for (const c of word2) { if (++cnt[c.charCodeAt(0) - 97] === 1) { ++need; } } const win: number[] = Array(26).fill(0); let [ans, l] = [0, 0]; for (const c of word1) { const i = c.charCodeAt(0) - 97; if (++win[i] === cnt[i]) { --need; } while (need === 0) { const j = word1[l].charCodeAt(0) - 97; if (win[j] === cnt[j]) { ++need; } --win[j]; ++l; } ans += l; } return ans; }