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 <= 104word1 and word2 consist only of lowercase English letters.This approach uses a sliding window to iterate over all possible substrings of word1. By maintaining character counts for substrings and word2, we determine if a substring can be rearranged to start with word2 as a prefix.
This Python solution uses a sliding window and a dictionary (Counter) to keep track of character frequencies. It adjusts the window size while ensuring all necessary characters from word2 are covered by the substring, incrementing the valid substring count when conditions meet.
JavaScript
The time complexity is O(n) where n is the length of word1, as each character is added and removed at most twice from the sliding window. The space complexity is O(1) as the size of the dictionary is bounded by the character set.
This approach involves utilizing prefix sums to accumulate character frequencies across word1. By comparing these accumulations with the necessary frequencies from word2, we can efficiently find valid rearrangements for substrings.
The Java solution employs a prefix sum array to track character frequencies as we traverse word1. It ensures that every substring window is checked against the character requirements from word2 with minimal recalibration of counts.
C++
The solution shows O(n) time complexity since each character in word1 is involved in prefix updates a fixed number of times. The space complexity is O(1), reflecting the fixed-size character frequency array.
| Approach | Complexity |
|---|---|
| Sliding Window with Character Count | The time complexity is O(n) where n is the length of |
| Prefix Sum with Character Frequency | The solution shows O(n) time complexity since each character in |
Leetcode - Count Binary Substrings (Python) • Timothy H Chang • 6,150 views views
Watch 9 more video solutions →Practice Count Substrings That Can Be Rearranged to Contain a String I with our built-in code editor and test cases.
Practice on FleetCode