Count Substrings That Can Be Rearranged to Contain a String I - Video Solutions

Problem Overview: You are given a string and another target string. The task is to count how many substrings can be rearranged so that the substring contains all characters of the target string. Since rearrangement is allowed, only the character frequencies matter, not their order.

Approach 1: Sliding Window with Character Count (O(n) time, O(1) space)

This approach uses the classic sliding window technique combined with a character frequency map. First compute the required frequency of each character from the target string. Expand the right pointer across the main string while updating counts in the window. When the window has at least the required frequency for every character, the substring can be rearranged to contain the target.

Once a valid window is found, every extension of that window to the right is also valid. If the current right index is r, then all substrings ending from r to n-1 work, so you add n - r to the answer. Then shrink the window from the left to find the next minimal valid window. Frequency checks are constant time using an array or hash table. The full scan runs in O(n) time with O(1) space since the alphabet size is fixed.

Approach 2: Prefix Sum with Character Frequency (O(26 · n log n) time, O(26 · n) space)

This method precomputes prefix frequency arrays for each character in the string using a string preprocessing technique. With prefix sums, you can quickly compute the frequency of any character inside a substring [l, r] in constant time. For each starting index l, search for the smallest r where the substring contains all required frequencies of the target string.

Once such an r is found, every larger ending index also forms a valid substring. Add n - r to the result and move to the next starting index. The frequency check uses prefix differences, and finding the minimal valid r can be done with binary search or incremental scanning. This approach is easier to reason about when you already have prefix frequency infrastructure but uses more memory.

Recommended for interviews: Sliding window with character counts is the expected solution. It runs in O(n) time, uses constant space, and demonstrates strong understanding of frequency tracking and window contraction. The prefix sum method is conceptually clean but heavier in both memory and implementation.