3573. Count Substrings That Can Be Rearranged To Contain A String I¶
3573. Count Substrings That Can Be Rearranged to Contain a String I
Medium
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.
Solution¶
class Solution {
public long validSubstringCount(String s1, String s2) {
long ans = 0;
int[] first = new int[26];
for(int i = 0; i < s2.length(); i++) first[s2.charAt(i)-'a']++;
int n = s1.length();
int[] second = new int[26];
for(int i = 0, j = 0; i < n; i++) {
while(j < n && !check(first, second)) {
second[s1.charAt(j)-'a']++;
j++;
}
if(check(first, second))
ans += n - j + 1;
second[s1.charAt(i) - 'a']--;
}
return ans;
}
private boolean check(int[] a, int[] b) {
for(int i = 0; i < a.length; i++) {
if(a[i] > b[i]) return false;
}
return true;
}
}
Complexity Analysis¶
- Time Complexity: O(?)
- Space Complexity: O(?)
Explanation¶
[Add detailed explanation here]