Count Substrings That Can Be Rearranged to Contain a String I

Count Substrings That Can Be Rearranged to Contain a String I - 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.

Input & Output

Example 1 — Basic Case

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

› Output: 1

💡 Note: Only one valid substring "bcc" at index 0-2. It can be rearranged as "bcc" → "abc" + "c" (abc as prefix)

Example 2 — Multiple Valid Substrings

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

› Output: 10

💡 Note: Valid substrings: "abc"(0-2), "abca"(0-3), "abcab"(0-4), "abcabc"(0-5), "bca"(1-3), "bcab"(1-4), "bcabc"(1-5), "cab"(2-4), "cabc"(2-5), "abc"(3-5)

Example 3 — No Valid Substrings

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

› Output: 7

💡 Note: word1 has enough characters for abc. Valid substrings include "abc"(0-2), "abca"(0-3), "abcab"(0-4), "bca"(1-3), "bcab"(1-4), "cab"(2-4)

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

word1="bcca", word2="abc" needs a≥1, b≥1, c≥1

Check Substrings

Examine each substring's character frequencies

Count Valid

Count substrings that can rearrange to have word2 as prefix

Key Takeaway

🎯 Key Insight: A substring is valid if its character frequencies meet or exceed word2's requirements

Asked in

G Google 25 M Microsoft 18

The key insight is that a substring is valid if it contains at least as many of each character as word2. Best approach is sliding window to avoid redundant frequency counting. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window	O(n²)	O(1)	Use expanding window to maintain character frequencies efficiently
Brute Force	O(n³)	O(1)	Check every substring by counting character frequencies

Sliding Window — Algorithm Steps

Fix left boundary of window
Expand right boundary one character at a time
Maintain running frequency count
Check if current window is valid after each expansion

Visualization

Tap to expand

Step-by-Step Walkthrough

Fix Start

Fix left boundary at position i

Expand Right

Add one character at a time to the right

Check Validity

After each expansion, check if window is valid

Code -

solution.c — C

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

int solution(char* word1, char* word2) {
    int n = strlen(word1);
    int m = strlen(word2);
    int count = 0;
    
    // Count frequency of characters in word2
    int word2Freq[26] = {0};
    for (int i = 0; i < m; i++) {
        word2Freq[word2[i] - 'a']++;
    }
    
    // For each starting position
    for (int i = 0; i < n; i++) {
        int windowFreq[26] = {0};
        
        // Expand window from position i
        for (int j = i; j < n; j++) {
            // Add current character to window
            windowFreq[word1[j] - 'a']++;
            
            // Check if window is large enough
            if (j - i + 1 < m) continue;
            
            // Check if current window is valid
            bool valid = true;
            for (int k = 0; k < 26; k++) {
                if (windowFreq[k] < word2Freq[k]) {
                    valid = false;
                    break;
                }
            }
            
            if (valid) count++;
        }
    }
    
    return count;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n²)

O(n) starting positions × O(n) expansions, but frequency check is O(1) amortized

⚠ Quadratic Growth

Space Complexity

O(1)

Only using frequency arrays of constant size (26 characters)

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 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

Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler