3298. Count Substrings That Can Be Rearranged to Contain a String II LeetCode Solution
In this guide, you will get 3298. Count Substrings That Can Be Rearranged to Contain a String II LeetCode Solution with the best time and space complexity. The solution to Count Substrings That Can Be Rearranged to Contain a String II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count Substrings That Can Be Rearranged to Contain a String II
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.
3298. Count Substrings That Can Be Rearranged to Contain a String II LeetCode Solution in C++
class Solution {
public:
// Same as 3297. Count Substrings That Can Be Rearranged to Contain a String I
long long validSubstringCount(string word1, string word2) {
long ans = 0;
int required = word2.length();
vector<int> count(26);
for (const char c : word2)
++count[c - 'a'];
for (int l = 0, r = 0; r < word1.length(); ++r) {
if (--count[word1[r] - 'a'] >= 0)
--required;
while (required == 0) {
// Add valid substrings containing word1[l..r] to the answer. They are
// word1[l..r], word1[l..r + 1], ..., word1[l..n - 1].
ans += word1.length() - r;
if (++count[word1[l++] - 'a'] > 0)
++required;
}
}
return ans;
}
}; /* code provided by PROGIEZ */
3298. Count Substrings That Can Be Rearranged to Contain a String II LeetCode Solution in Java
class Solution {
// Same as 3297. Count Substrings That Can Be Rearranged to Contain a String I
public long validSubstringCount(String word1, String word2) {
long ans = 0;
int required = word2.length();
int[] count = new int[26];
for (final char c : word2.toCharArray())
++count[c - 'a'];
for (int l = 0, r = 0; r < word1.length(); ++r) {
if (--count[word1.charAt(r) - 'a'] >= 0)
--required;
while (required == 0) {
// Add valid substrings containing word1[l..r] to the answer. They are
// word1[l..r], word1[l..r + 1], ..., word1[l..n - 1].
ans += word1.length() - r;
if (++count[word1.charAt(l++) - 'a'] > 0)
++required;
}
}
return ans;
}
} // code provided by PROGIEZ
3298. Count Substrings That Can Be Rearranged to Contain a String II LeetCode Solution in Python
class Solution:
# Same as 3297. Count Substrings That Can Be Rearranged to Contain a String I
def validSubstringCount(self, word1: str, word2: str) -> int:
ans = 0
count = collections.Counter(word2)
required = len(word2)
l = 0
for r, c in enumerate(word1):
count[c] -= 1
if count[c] >= 0:
required -= 1
while required == 0:
# Add valid substrings containing word1[l..r] to the answer. They are
# word1[l..r], word1[l..r + 1], ..., word1[l..n - 1].
ans += len(word1) - r
count[word1[l]] += 1
if count[word1[l]] > 0:
required += 1
l += 1
return ans # code by PROGIEZ
