Count Substrings That Can Be Rearranged to Contain a String I

Count Substrings That Can Be Rearranged to Contain a String I

What is this problem about?

The Count Substrings That Can Be Rearranged to Contain a String I interview question asks you to count how many substrings of a main string s1 can be rearranged (i.e., contain at least the same characters) to include string s2 as a subset.

In simpler terms, if s2 requires two 'a's and one 'b', any substring of s1 that has at least two 'a's and one 'b' is considered a "valid" substring. Note that the order of characters in the substring doesn't matter, which is the hallmark of an anagram or rearrangement problem.

Why is this asked in interviews?

Amazon frequently uses this type of problem to evaluate a candidate's mastery of the sliding window interview pattern. It tests the ability to maintain a dynamic frequency count of characters and efficiently determine when a window satisfies a specific condition. It also requires the candidate to understand that if a substring from index $i$ to $j$ is valid, then all substrings from $i$ to $k$ (where $k > j$) are also valid, provided they stay within the bounds of the original string.

Algorithmic pattern used

This problem leverages the Sliding Window and Hash Table (Frequency Map) patterns.

1. Create a frequency map for s2.
2. Use two pointers to define a window in s1.
3. Expand the right pointer until the current window contains all characters of s2 with the required frequencies.
4. Once valid, every substring starting at the current left pointer and ending at any index from the current right pointer to the end of s1 is also valid.
5. Contract the window from the left to find the next smallest valid window.

Example explanation

s1 = "abcabc", s2 = "aa"

1. We need two 'a's.
2. Window [0,3] is "abca". It has two 'a's. This is valid.
3. Because "abca" is valid, "abcab" and "abcabc" are also valid (3 substrings starting at index 0).
4. Move left pointer. Window [1,3] is "bca". Only one 'a'. Not valid.
5. Move right pointer... and so on.

Common mistakes candidates make

• Counting only the smallest window: Forgetting that if a window is valid, expanding it further to the right keeps it valid.
• Inefficient frequency checks: Re-scanning the entire frequency map on every window move instead of using a "counter" variable to track how many unique characters have met their target frequency.
• Handling duplicates: Miscounting when s2 has multiple instances of the same character.

Interview preparation tip

When dealing with "Count Substrings" problems where adding more characters preserves the condition, always calculate the count as (n - right_pointer) the moment your window becomes valid. This turns an $O(N^2)$ problem into an $O(N)$ solution.