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 same characters as word2 with the required frequencies, allowing them to be rearranged to have "abc" as a prefix.

The key insight is that for a substring to be valid, it must contain at least all the characters of word2 with their respective frequencies. Any additional characters in the substring can be placed after the rearranged word2 prefix.

Intuition

The key observation is that for a substring to be rearrangeable with word2 as a prefix, it must contain at least all characters from word2 with their required frequencies. Any extra characters can simply be placed after the prefix.

This transforms the problem into finding all substrings of word1 that contain at least the character frequencies of word2. This is a classic sliding window problem pattern.

Consider how we can efficiently count valid substrings. If we fix a right endpoint r and find the minimum left endpoint l such that the substring [l, r] contains all required characters, then all substrings ending at r with starting positions from 0 to l-1 are also valid (since they contain even more characters). This gives us l valid substrings for this particular right endpoint.

The sliding window technique naturally fits here:

1. Expand the window by moving the right pointer and adding characters
2. When the window contains all required characters from word2, we have a valid window
3. Shrink from the left to find the minimum valid window ending at the current right position
4. Count all valid substrings ending at the current right position

The trick is maintaining two frequency counters - one for word2's requirements (cnt) and one for our current window (win). We use a need variable to track how many unique characters still need to reach their required frequency. When need becomes 0, we know our window is valid.

For each position, we shrink the left boundary until the window becomes invalid (missing required characters), then add l to our answer since positions [0, l-1] all form valid substrings when paired with the current right endpoint.

Learn more about Sliding Window patterns.

Solution Approach

We implement a sliding window algorithm with two pointers to efficiently count valid substrings.

Initial Setup:

• First check if len(word1) < len(word2) - if true, return 0 immediately since no valid substring can exist
• Create a frequency counter cnt for word2 using Counter(word2) to track required character frequencies
• Initialize need = len(cnt) to track how many unique characters still need to reach their required frequency
• Initialize ans = 0 for the answer, l = 0 for the left pointer, and win = Counter() for the current window's character frequencies

Main Algorithm: For each character c at position r in word1:

1. Expand the window: Add character c to the window by incrementing win[c] += 1

2. Check if requirement met: If win[c] == cnt[c], it means character c now meets its required frequency, so decrement need -= 1

3. Handle valid windows: When need == 0, the current window [l, r] contains all required characters:

   • Shrink from the left to find the minimum valid window
   • While shrinking:
     • If win[word1[l]] == cnt[word1[l]], removing this character will break the validity, so increment need += 1
     • Decrement win[word1[l]] -= 1 to remove the leftmost character from the window
     • Move left pointer forward: l += 1
   • The loop exits when the window becomes invalid (need > 0)

4. Count valid substrings: After shrinking, add l to the answer. This represents all substrings ending at position r with starting positions from 0 to l-1 (inclusive), since they all contain the required characters

Example Walkthrough: If word1 = "aaacb" and word2 = "abc":

• When we reach position 4 (the 'b'), the window [2, 4] = "acb" contains all required characters
• After shrinking, l = 3, meaning substrings [0,4], [1,4], and [2,4] are all valid
• We add 3 to our answer

The time complexity is O(n) where n = len(word1), as each character is visited at most twice (once by right pointer, once by left pointer). The space complexity is O(1) since we use fixed-size counters (at most 26 characters for lowercase English letters).

Example Walkthrough

Let's walk through a concrete example with word1 = "bcca" and word2 = "abc".

Initial Setup:

• cnt = {'a': 1, 'b': 1, 'c': 1} (frequency requirements from word2)
• need = 3 (we need to satisfy 3 unique character requirements)
• win = {} (empty window counter)
• l = 0, ans = 0

Step-by-step execution:

r = 0, c = 'b':

• Add 'b' to window: win = {'b': 1}
• Check: win['b'] == cnt['b'] (1 == 1), so need = 2
• Since need > 0, window is not valid yet
• No substrings to count

r = 1, c = 'c':

• Add 'c' to window: win = {'b': 1, 'c': 1}
• Check: win['c'] == cnt['c'] (1 == 1), so need = 1
• Since need > 0, window is not valid yet
• No substrings to count

r = 2, c = 'c':

• Add 'c' to window: win = {'b': 1, 'c': 2}
• Check: win['c'] != cnt['c'] (2 != 1), so need stays 1
• Since need > 0, window is not valid yet
• No substrings to count

r = 3, c = 'a':

• Add 'a' to window: win = {'b': 1, 'c': 2, 'a': 1}
• Check: win['a'] == cnt['a'] (1 == 1), so need = 0
• Window is valid! Current window is [0, 3] = "bcca"
• Now shrink from left:
  • At l = 0: character 'b' has win['b'] = 1 = cnt['b'], removing it breaks validity
  • Set need = 1, decrement win['b'] = 0, move l = 1
  • Exit shrinking loop since need > 0
• Add l = 1 to answer: ans = 1
• This counts the substring [0, 3] = "bcca" (which can be rearranged to "abcc")

Final answer: 1

The only valid substring is "bcca" itself, which contains exactly the characters needed ('a', 'b', 'c') to form "abc" as a prefix after rearrangement.

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 to traverse word1 once, where each character is visited at most twice (once when expanding the window and once when shrinking it), resulting in O(n) operations. 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 the character frequencies of word2 and win to track the current window's character frequencies. Since the problem deals with lowercase English letters, the size of the character set is at most 26, making the space complexity O(1) or constant space.

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

Common Pitfalls

Pitfall 1: Incorrectly Counting Valid Substrings

The Problem: A common mistake is misunderstanding what result += left represents. Developers often think they need to count substrings only when chars_needed == 0, leading to incorrect implementations like:

# INCORRECT approach
while chars_needed == 0:
    result += 1  # Wrong! This only counts one substring per valid window
    # ... shrink window logic

Why It's Wrong: When we find a valid window ending at position right, ALL substrings ending at right with starting positions from 0 to left-1 are valid. The incorrect approach only counts the minimal valid window.

The Solution: After shrinking the window to find the leftmost valid position, add left to the result. This accounts for all valid substrings ending at the current right position:

# CORRECT approach
while chars_needed == 0:
    # Shrink window to find minimum valid window
    if window_freq[word1[left]] == target_freq[word1[left]]:
        chars_needed += 1
    window_freq[word1[left]] -= 1
    left += 1

# Add all valid substrings ending at 'right'
result += left

Pitfall 2: Mishandling Character Frequency Comparison

The Problem: When checking if a character's frequency matches the target, developers might use:

# INCORRECT - doesn't handle characters not in word2
if char in target_freq and window_freq[char] == target_freq[char]:
    chars_needed -= 1

Why It's Wrong: Python's Counter returns 0 for missing keys, so target_freq[char] returns 0 for characters not in word2. The code should handle this case correctly without explicit checks.

The Solution: The original code handles this elegantly:

# CORRECT - Counter returns 0 for missing keys
if window_freq[char] == target_freq[char]:
    chars_needed -= 1

This works because:

• If char is not in word2, target_freq[char] = 0
• When window_freq[char] becomes 0 (or starts at 0 and increments to 1), the condition won't match
• Only when both frequencies match (including the case where both are 0) do we adjust chars_needed

Pitfall 3: Over-decrementing chars_needed

The Problem: Some implementations might decrement chars_needed every time a required character is added:

# INCORRECT
if char in target_freq:
    window_freq[char] += 1
    if window_freq[char] <= target_freq[char]:
        chars_needed -= 1  # Wrong! This decrements for every occurrence

Why It's Wrong: chars_needed tracks the number of unique characters that have reached their target frequency, not the total count of characters. Decrementing for every occurrence would make chars_needed negative and break the algorithm.

The Solution: Only decrement chars_needed when a character's frequency exactly matches the target:

# CORRECT
window_freq[char] += 1
if window_freq[char] == target_freq[char]:  # Exact match only
    chars_needed -= 1

This ensures each unique character in word2 contributes exactly once to reducing chars_needed from its initial value.