Problem Description

You are given two strings word1 and word2.

A string x is considered valid if it can be rearranged (its characters can be reordered) to have word2 as a prefix. In other words, after rearranging the characters of x, the resulting string should start with word2.

Your task is to find and return the total number of valid substrings of word1. A substring is a contiguous sequence of characters within word1.

For example, if word1 = "abcabc" and word2 = "abc", then substrings like "abc", "bca", "cab", "abca", "bcab", "cabc", and "abcabc" are all valid because they contain at least the characters 'a', 'b', and 'c' with the required frequencies, allowing them to be rearranged to have "abc" as a prefix.

Important constraint: The memory limits for this problem are smaller than usual, so you must implement a solution with linear runtime complexity O(n).

The key insight is that for a substring to be valid, it must contain at least all the characters from word2 with their respective frequencies. Once a substring contains all required characters, it can be rearranged to place word2 at the beginning.

Intuition

The core observation is that a substring is valid if it contains at least all characters from word2 with their required frequencies. Once we have these characters, we can rearrange them to form word2 as a prefix.

This immediately suggests using a sliding window approach. But here's the key insight: instead of finding all valid windows separately, we can be clever about counting them.

Consider when we have a window [l, r] that just barely contains all required characters. If we extend the right boundary to r+1, we still have a valid window. More importantly, if [l, r] is valid, then any window [l', r] where l' < l is also valid because it contains even more characters.

This leads us to the counting strategy: for each right boundary position r, we want to find the rightmost left boundary l such that [l, r] is still valid. Then all windows [0, r], [1, r], ..., [l-1, r] are valid, giving us exactly l valid substrings ending at position r.

The algorithm works by:

1. Expanding the window by moving the right pointer and adding characters
2. When we have all required characters (a valid window), we shrink from the left as much as possible while maintaining validity
3. Once we can't shrink anymore (removing one more character would make it invalid), we count all valid substrings ending at the current right position

The use of need counter is elegant - it tracks how many distinct characters still need to reach their required frequency. When need = 0, we have a valid window. When we shrink and lose a required character, need becomes positive again, signaling we've found the boundary.

This approach ensures we count each valid substring exactly once and achieves the required O(n) time complexity since each character is visited at most twice (once by right pointer, once by left pointer).

Learn more about Sliding Window patterns.

Solution Approach

The solution uses a sliding window technique with two pointers to efficiently count valid substrings.

Initial Setup:

• First, check if len(word1) < len(word2). If true, return 0 since it's impossible to have valid substrings.
• Create a counter cnt to store the frequency of each character in word2.
• Initialize need = len(cnt), which tracks how many distinct characters from word2 we still need to match their required frequencies.
• Initialize win as a counter for the current window, ans = 0 for the result, and l = 0 for the left boundary.

Main Algorithm: We iterate through each character in word1 using it as the right boundary of our window:

1. Expand the window: For each character c at position r:

   • Add it to the window: win[c] += 1
   • Check if this character helps us meet a requirement: if win[c] == cnt[c], we've just satisfied the frequency requirement for character c, so decrement need -= 1

2. Shrink when valid: When need == 0 (all requirements met):

   • Try to shrink from the left to find the smallest valid window ending at r
   • Before removing word1[l] from the window:
     • If win[word1[l]] == cnt[word1[l]], removing this character will break a requirement, so increment need += 1
     • Decrement the count: win[word1[l]] -= 1
     • Move left pointer: l += 1
   • This loop continues until need > 0, meaning we've found the rightmost l where [l, r] is still valid

3. Count valid substrings: After shrinking, add l to the answer. This represents all valid substrings ending at position r:

   • [0, r], [1, r], ..., [l-1, r] are all valid (total of l substrings)
   • [l, r] and beyond are not valid (don't contain all required characters)

Key Insights:

• The need counter elegantly tracks validity: when it's 0, we have all required characters with correct frequencies
• By shrinking to find the rightmost valid left boundary, we can count all valid substrings ending at each position in O(1) time
• Each character is visited at most twice (once by right pointer, once by left pointer), ensuring O(n) time complexity
• The space complexity is O(1) since we only use fixed-size counters (at most 26 characters)

The algorithm efficiently counts all valid substrings by recognizing that if [l, r] is the minimal valid window ending at r, then there are exactly l valid substrings ending at that position.

Example Walkthrough

Let's walk through the algorithm with word1 = "bcabc" and word2 = "abc".

Initial Setup:

• cnt = {'a': 1, 'b': 1, 'c': 1} (frequency of characters in word2)
• need = 3 (we need to match 3 distinct characters)
• win = {} (empty window counter)
• ans = 0, l = 0

Step-by-step execution:

r = 0, character 'b':

• Add 'b' to window: win = {'b': 1}
• Since win['b'] == cnt['b'] (both are 1), we satisfied 'b': need = 2
• need > 0, so we don't shrink
• ans += 0 (no valid substrings yet)

r = 1, character 'c':

• Add 'c' to window: win = {'b': 1, 'c': 1}
• Since win['c'] == cnt['c'] (both are 1), we satisfied 'c': need = 1
• need > 0, so we don't shrink
• ans += 0 (still no valid substrings)

r = 2, character 'a':

• Add 'a' to window: win = {'b': 1, 'c': 1, 'a': 1}
• Since win['a'] == cnt['a'] (both are 1), we satisfied 'a': need = 0
• Now need == 0, we have a valid window [0,2] = "bca"
• Try to shrink:
  • Check word1[0] = 'b': if we remove it, win['b'] would become 0, breaking the requirement
  • Since win['b'] == cnt['b'], removing it would make window invalid: need = 1
  • Remove 'b': win = {'b': 0, 'c': 1, 'a': 1}, l = 1
  • Stop shrinking since need > 0
• ans += 1 (substring [0,2] = "bca" is valid)

r = 3, character 'b':

• Add 'b' to window: win = {'b': 1, 'c': 1, 'a': 1}
• Since win['b'] == cnt['b'] (both are 1), we satisfied 'b' again: need = 0
• need == 0, valid window [1,3] = "cab"
• Try to shrink:
  • Check word1[1] = 'c': if we remove it, win['c'] would become 0
  • Since win['c'] == cnt['c'], removing it would break requirement: need = 1
  • Remove 'c': win = {'b': 1, 'c': 0, 'a': 1}, l = 2
  • Stop shrinking since need > 0
• ans += 2 (substrings [0,3] = "bcab" and [1,3] = "cab" are valid)
• Total: ans = 3

r = 4, character 'c':

• Add 'c' to window: win = {'b': 1, 'c': 1, 'a': 1}
• Since win['c'] == cnt['c'] (both are 1), we satisfied 'c' again: need = 0
• need == 0, valid window [2,4] = "abc"
• Try to shrink:
  • Check word1[2] = 'a': if we remove it, win['a'] would become 0
  • Since win['a'] == cnt['a'], removing it would break requirement: need = 1
  • Remove 'a': win = {'b': 1, 'c': 1, 'a': 0}, l = 3
  • Stop shrinking since need > 0
• ans += 3 (substrings [0,4] = "bcabc", [1,4] = "cabc", and [2,4] = "abc" are valid)
• Total: ans = 6

Final Result: 6 valid substrings

The valid substrings are:

1. "bca" (can be rearranged to "abc")
2. "bcab" (can be rearranged to "abcb" with "abc" prefix)
3. "cab" (can be rearranged to "abc")
4. "bcabc" (can be rearranged to "abcbc" with "abc" prefix)
5. "cabc" (can be rearranged to "abc" + "c")
6. "abc" (already has all required characters)

Solution Implementation

Time and Space Complexity

The time complexity is O(n + m), where n is the length of word1 and m is the length of word2. The algorithm first counts the characters in word2 using Counter, which takes O(m) time. Then it uses a sliding window approach with two pointers that traverse word1 once. The right pointer moves through all n characters exactly once, and the left pointer also moves at most n times throughout the entire execution, giving us O(n) for the main loop. Therefore, the total time complexity is O(n + m).

The space complexity is O(|Σ|), where Σ represents the character set. The algorithm uses two Counter objects: cnt to store character frequencies from word2 and win to track the current window's character frequencies. Since the problem deals with lowercase English letters, the maximum number of distinct characters is 26, making the space complexity O(1) or constant space. Even though we store counters, their size is bounded by the alphabet size rather than the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Counting Logic

The Problem: Many developers incorrectly assume that when need == 0 (window is valid), they should count ALL substrings within the current window [left, right]. This leads to code like:

if chars_needed == 0:
    # WRONG: This counts internal substrings multiple times
    result += (right - left + 1)

Why It's Wrong: This approach counts substrings multiple times. For example, if [0, 5] is valid, this would count substring [1, 4] here. But when we later process [1, 4] directly, we'd count it again.

The Correct Approach: Count only substrings that END at the current position right. After shrinking to find the smallest valid window [left, right], we know that:

• [0, right], [1, right], ..., [left-1, right] are all valid (total of left substrings)
• [left, right] onwards are invalid (missing required characters)

Pitfall 2: Incorrect Window Shrinking Condition

The Problem: Some implementations shrink the window while it remains valid:

# WRONG: Shrinks while window is still valid
while chars_needed == 0:
    result += 1  # or some counting logic
    # shrink window...

Why It's Wrong: This approach finds valid windows but doesn't correctly count all valid substrings. It might miss counting larger valid substrings that contain the minimal window.

The Correct Approach: Shrink until the window becomes invalid, then count based on the last valid position:

while chars_needed == 0:
    # First check if removing would break validity
    if window_count[word1[left]] == target_count[word1[left]]:
        chars_needed += 1
    # Then remove and move pointer
    window_count[word1[left]] -= 1
    left += 1
# After loop: left is now at first position that makes window invalid
result += left  # Count all valid substrings ending at right

Pitfall 3: Overcounting Due to Character Frequency Satisfaction

The Problem: Incorrectly decrementing chars_needed every time a character count increases:

# WRONG: Decrements even when already satisfied
window_count[char] += 1
if char in target_count and window_count[char] >= target_count[char]:
    chars_needed -= 1

Why It's Wrong: If a character already has sufficient count (e.g., we need 2 'a's and already have 3), adding another 'a' would incorrectly decrement chars_needed again, leading to negative values or incorrect validity checks.

The Correct Approach: Only decrement chars_needed when we EXACTLY meet the requirement:

window_count[char] += 1
# Only when we go from insufficient to exactly sufficient
if window_count[char] == target_count[char]:
    chars_needed -= 1

Similarly, when shrinking, only increment chars_needed when we go from exactly sufficient to insufficient:

if window_count[word1[left]] == target_count[word1[left]]:
    chars_needed += 1
window_count[word1[left]] -= 1