Skip to main content
Talentd

Count Substrings That Can Be Rearranged to Contain a String II - Solution & Explanation

HardHash TableStringSliding Window18 min read
Practice this problem

Problem Statement

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.

Note that the memory limits in this problem are smaller than usual, so you must implement a solution with a linear runtime complexity.

 

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 <= 106
  • 1 <= word2.length <= 104
  • word1 and word2 consist only of lowercase English letters.

Approach Overview

Problem Overview: You are given two strings. Count how many substrings of the main string can be rearranged so that the target string appears inside it. A substring is valid if its character frequencies contain at least the same counts as the target string.

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

This approach uses a sliding window combined with a character frequency counter. First compute the frequency of each character in the target string. Expand the right pointer across the main string while maintaining a window frequency array. Once the window satisfies all required character counts, every extension of this window to the right also remains valid. Shrink the left pointer to find the minimal valid window while accumulating the number of valid substrings. Since each pointer moves at most n times, the algorithm runs in O(n) time with O(1) space (fixed alphabet).

Approach 2: Two-Pointer Technique (O(n) time, O(1) space)

The two-pointer technique is a slightly different framing of the same idea. Maintain two indices representing the current substring boundaries and track character counts using an array or hash table. Move the right pointer to include characters until the substring contains all characters required by the target string. Once valid, move the left pointer forward while counting all substrings that still satisfy the requirement. The key insight: if a window starting at l and ending at r is valid, then any window ending after r is also valid. This lets you add multiple substrings in constant time.

Both methods rely on maintaining character frequencies and verifying whether the window covers the target string requirements. Using fixed-size arrays for lowercase characters avoids expensive map operations and keeps the algorithm linear. The logic is commonly implemented in languages like Python, C++, Java, and JavaScript using simple arrays indexed by character codes.

Recommended for interviews: The sliding window approach is the expected solution. Interviewers want to see that you recognize the substring counting pattern where a valid window implies multiple valid extensions. Demonstrating the frequency check and efficient window contraction shows strong understanding of string processing and sliding window optimization.

Approach 1: Sliding Window with Frequency Count

This approach utilizes a sliding window to manage the substrings of word1 and checks their character counts against the count of characters in word2. By keeping track of character counts inside the window and comparing with the required counts in word2, we can efficiently identify valid substrings.

The solution initiates character counts for word2 and uses them as a baseline. We then use a sliding window with a length equal to word2. As we expand the window by adding a character and contracting it by removing a character when it exceeds the length, we maintain the character count of the window. Whenever the character counts in the current window match or exceed the counts in word2, we have a valid substring.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n), where n is the length of word1, due to the single pass required to maintain and check character counts.
Space Complexity: O(1), as we use a fixed space count dictionary which does not scale with input size.

Try this approach in the editor →

Approach 2: Two-pointer Technique

This approach uses two pointers to denote the boundaries of a window on word1 and adjusts dynamically while maintaining valid sets of character counts. We increment the right pointer to expand the window and adjust the left pointer to contract it, ensuring it matches or exceeds word2 prefix requirement.

The solution employs two HashMaps to track counts within a sliding window on word1 and to track the necessary counts from word2. It allows dynamic adjustment using left and right pointers to ensure the window maintains the required conditions.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n), where n is the length of word1, facilitated by the two-pointer technique.
Space Complexity: O(1), considering fixed space is used for character counts similar to the Python solution.

Try this approach in the editor →

Approach 3: Sliding Window

The problem is essentially to find how many substrings in word1 contain all the characters in word2. We can use a sliding window to handle this.

First, if the length of word1 is less than the length of word2, then it is impossible for word1 to contain all the characters of word2, so we directly return 0.

Next, we use a hash table or an array of length 26 called cnt to count the occurrences of characters in word2. Then, we use need to record how many more characters are needed to meet the condition, initialized to the length of cnt.

We then use a sliding window win to record the occurrences of characters in the current window. We use ans to record the number of substrings that meet the condition, and l to record the left boundary of the window.

We traverse each character in word1. For the current character c, we add it to win. If the value of win[c] equals cnt[c], it means the current window already contains one of the characters in word2, so we decrement need by one. If need equals 0, it means the current window contains all the characters in word2. We need to shrink the left boundary of the window until need is greater than 0. Specifically, if win[word1[l]] equals cnt[word1[l]], it means the current window contains one of the characters in word2. After shrinking the left boundary, it no longer meets the condition, so we increment need by one and decrement win[word1[l]] by one. Then, we increment l by one. At this point, the window is [l, r]. For any 0 leq l' < l, [l', r] are substrings that meet the condition, and there are l such substrings, which we add to the answer.

After traversing all characters in word1, we get the answer.

The time complexity is O(n + m), where n and m are the lengths of word1 and word2, respectively. The space complexity is O(|\Sigma|), where \Sigma is the character set. Here, it is the set of lowercase letters, so the space complexity is constant.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window with Frequency Count

Time Complexity: O(n), where n is the length of word1, due to the single pass required to maintain and check character counts.
Space Complexity: O(1), as we use a fixed space count dictionary which does not scale with input size.

Two-pointer Technique

Time Complexity: O(n), where n is the length of word1, facilitated by the two-pointer technique.
Space Complexity: O(1), considering fixed space is used for character counts similar to the Python solution.

Sliding Window—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window with Frequency CountO(n)O(1)Best general solution for substring counting with character constraints
Two-Pointer TechniqueO(n)O(1)Useful when implementing minimal valid window logic and counting extensions

Video Solution

3298. Count Substrings That Can Be Rearranged to Contain a String II | Weekly Leetcode 416 • codingMohan • 948 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Count Substrings That Can Be Rearranged to Contain a String II easy or hard?
Count Substrings That Can Be Rearranged to Contain a String II is classified as a Hard problem. The challenge comes from recognizing the substring counting optimization and correctly maintaining frequency constraints while adjusting the sliding window.
Count Substrings That Can Be Rearranged to Contain a String II Python/Java solution
Implement the sliding window logic using an integer array of size 26 for lowercase letters. Update counts as the right pointer expands and decrease them when the left pointer moves. The same algorithm works across Python, Java, C++, and JavaScript with only minor syntax differences.
How to solve Count Substrings That Can Be Rearranged to Contain a String II in O(n)?
Use a sliding window and track the frequency of characters required by the target string. Expand the right pointer until the window contains all required counts. Once the condition is satisfied, every longer substring starting at the same left index remains valid, so you add multiple substrings at once and then shrink the window.
What is the best approach for Count Substrings That Can Be Rearranged to Contain a String II?
The most efficient approach uses a sliding window with character frequency counting. Maintain counts for the target string and expand a window over the main string until the window satisfies all required characters. Once valid, count all substrings extending from that window and shrink the left boundary. This method runs in O(n) time with O(1) space for a fixed alphabet.
Is Count Substrings That Can Be Rearranged to Contain a String II asked at Google/Amazon/Meta?
Problems involving sliding window substring counting and frequency constraints frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test your ability to manage dynamic windows and optimize brute-force substring checks into linear-time solutions.
What data structure is used in Count Substrings That Can Be Rearranged to Contain a String II?
The solution primarily uses frequency arrays or hash tables to track character counts. Combined with the sliding window technique, these structures allow constant-time updates and quick checks to verify whether the window satisfies the target string requirements.
What is the time complexity of Count Substrings That Can Be Rearranged to Contain a String II?
The optimal solution runs in O(n) time where n is the length of the main string. Each pointer in the sliding window moves at most once across the string. Space complexity is O(1) because the algorithm stores character frequencies in a fixed-size array.

Ready to solve this problem?

Practice Count Substrings That Can Be Rearranged to Contain a String II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Window Substring