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 <= 1051 <= 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.
Python3
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
Java
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;
}
}
C++
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;
}
};
Go
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
}
TypeScript
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;
}