Count Substrings That Can Be Rearranged to Contain a String I
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through every possible substring of word1. For each substring, we calculate its character frequency and check if it meets the criteria to be a "valid" string. A substring is considered valid if its character counts are greater than or equal to the character counts of word2 for every character in the alphabet. While straightforward, this method is computationally expensive.
Algorithm
- Pre-calculate the character frequency map of
word2, let's call itfreq2. - Initialize a counter for valid substrings,
count, to 0. - Use nested loops to generate all substrings of
word1. The outer loop iterates through the starting indexifrom0ton-1, and the inner loop iterates through the ending indexjfromiton-1. - For each substring
word1[i...j], maintain a running character frequency map,currentFreq. - After adding
word1.charAt(j)to the window, check ifcurrentFreqhas at least as many of each character asfreq2. - If the condition is met, it means the substring
word1[i...j]is valid, so increment thecount. - After iterating through all substrings, return the total
count.
Walkthrough
The brute-force method systematically checks every substring. We can optimize the process slightly by not re-calculating the frequency map for each substring from scratch. For a fixed starting point i, as we extend the substring by incrementing the end point j, we can update the frequency map of the current substring in O(1) time. Then, for each new substring word1[i...j], we perform a check against the frequency map of word2.
class Solution { public long countSubstrings(String word1, String word2) { int n = word1.length(); int m = word2.length(); long count = 0; int[] freq2 = new int[26]; for (char c : word2.toCharArray()) { freq2[c - 'a']++; } for (int i = 0; i < n; i++) { int[] currentFreq = new int[26]; for (int j = i; j < n; j++) { currentFreq[word1.charAt(j) - 'a']++; if (isSufficient(currentFreq, freq2)) { count++; } } } return count; } private boolean isSufficient(int[] freq1, int[] freq2) { for (int i = 0; i < 26; i++) { if (freq1[i] < freq2[i]) { return false; } } return true; }}Complexity
Time
O(N^2 * C), where N is the length of `word1` and C is the size of the character set (26). The two nested loops iterate through all O(N^2) substrings, and for each, the check takes O(C) time.
Space
O(C), where C is the size of the character set (26). This space is used to store the frequency maps.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem for small inputs.
Cons
This approach is too slow for the given constraints (
word1.lengthup to 10^5), as an O(N^2) complexity will lead to a 'Time Limit Exceeded' error.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.