Welcome to Subscribe On Youtube
3297. Count Substrings That Can Be Rearranged to Contain a String I
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
.
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 <= 10^{5}
1 <= word2.length <= 10^{4}
word1
andword2
consist 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) int64 { }

function validSubstringCount(word1: string, word2: string): number {}