Count Substrings That Can Be Rearranged to Contain a String II

Count Substrings That Can Be Rearranged to Contain a String II - Problem

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.

Input & Output

Example 1 — Basic Valid Substring

$ Input: word1 = "bcda", word2 = "abc"

› Output: 1

💡 Note: The substring "bcda" contains all characters needed (a=1, b=1, c=1) to rearrange and have "abc" as prefix. Only 1 valid substring exists.

Example 2 — Multiple Valid Substrings

$ Input: word1 = "abcabc", word2 = "ab"

› Output: 10

💡 Note: Many substrings contain at least 1 'a' and 1 'b': "ab", "abc", "abca", "abcab", "abcabc", "bc"+next chars, etc. Total count is 10.

Example 3 — No Valid Substrings

$ Input: word1 = "xyz", word2 = "abc"

› Output: 0

💡 Note: No substring of "xyz" contains the required characters a, b, c to form "abc" as prefix.

Constraints

1 ≤ word2.length ≤ word1.length ≤ 10⁵
word1 and word2 consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

word1 provides characters, word2 defines requirements

Substring Validation

Check if substring can be rearranged to have word2 as prefix

Count Result

Sum all valid substrings

Key Takeaway

🎯 Key Insight: A substring is valid if it contains at least as many of each character as required by word2

Asked in

G Google 35 f Meta 28 a Amazon 22

The key insight is that a substring can form word2 as prefix if it contains at least as many of each character as word2 requires. Best approach uses sliding window with early termination optimization. Time: O(n²), Space: O(k) where k is alphabet size.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(k)	Check every possible substring by counting character frequencies
Sliding Window Optimization	O(n²)	O(k)	Use expanding and contracting windows to efficiently count valid substrings

Brute Force — Algorithm Steps

Generate all possible substrings
Count character frequency for each substring
Check if substring can be rearranged to have word2 as prefix

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all O(n²) possible substrings

Count Characters

For each substring, count character frequencies

Validate

Check if substring contains enough characters to form word2

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(char* word1, char* word2) {
    int n = strlen(word1);
    int word2Count[26] = {0};
    
    // Count characters in word2
    for (int i = 0; word2[i]; i++) {
        word2Count[word2[i] - 'a']++;
    }
    
    long long count = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int substringCount[26] = {0};
            
            // Count characters in substring
            for (int k = i; k <= j; k++) {
                substringCount[word1[k] - 'a']++;
            }
            
            // Check if substring can be rearranged to have word2 as prefix
            int valid = 1;
            for (int k = 0; k < 26; k++) {
                if (substringCount[k] < word2Count[k]) {
                    valid = 0;
                    break;
                }
            }
            
            if (valid) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char word1[100001], word2[100001];
    fgets(word1, sizeof(word1), stdin);
    fgets(word2, sizeof(word2), stdin);
    word1[strcspn(word1, "\n")] = 0;
    word2[strcspn(word2, "\n")] = 0;
    
    long long result = solution(word1, word2);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) substrings × O(n) character counting for each

⚠ Quadratic Growth

Space Complexity

O(k)

Hash map to store character frequencies, k = alphabet size

✓ Linear Space

23.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler