Permutation in String - Practice Coding Problems

Permutation in String - Problem

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

A permutation is a rearrangement of characters. For example, "abc" has permutations "abc", "acb", "bac", "bca", "cab", and "cba".

Input & Output

Example 1 — Basic Permutation Found

$ Input: s1 = "ab", s2 = "eidbaooo"

› Output: true

💡 Note: s2 contains "ba" which is a permutation of "ab" (same characters: a=1, b=1)

Example 2 — No Permutation

$ Input: s1 = "ab", s2 = "eidboaoo"

› Output: false

💡 Note: No substring of s2 with length 2 has the same character frequencies as "ab"

Example 3 — Exact Match

$ Input: s1 = "adc", s2 = "dcda"

› Output: true

💡 Note: s2 contains "dcd" which has characters d=2, c=1 but "adc" has a=1, d=1, c=1. Actually "cda" has c=1, d=1, a=1 which matches "adc"

Constraints

1 ≤ s1.length, s2.length ≤ 10⁴
s1 and s2 consist of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

s1="ab" (need to find permutation), s2="eidbaooo" (search space)

Process

Check character frequencies of substrings

Output

Found "ba" which has same frequencies as "ab"

Key Takeaway

🎯 Key Insight: Instead of generating permutations, compare character frequency counts using sliding window

Asked in

f Facebook 45 M Microsoft 38 G Google 32

The key insight is that instead of generating all permutations, we can check if any substring has the same character frequencies as s1. The optimal approach uses a sliding window to efficiently track frequencies as we move through s2. Time: O(n + m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count - Check All Substrings	O(n × m)	O(1)	Compare character frequencies of s1 with every substring of s2 of same length
Brute Force - Generate All Permutations	O(n! × m)	O(n!)	Generate all permutations of s1 and check if any exists as substring in s2
Sliding Window - Optimal Solution	O(n + m)	O(1)	Use sliding window to efficiently track character frequencies without recalculating

Frequency Count - Check All Substrings — Algorithm Steps

Count character frequencies in s1
Check every substring of s2 with length equal to s1
Compare frequency counts for each substring

Visualization

Tap to expand

Step-by-Step Walkthrough

Count s1

Get character frequencies of s1

Check Substrings

Compare frequencies of each substring

Match Found

Return true when frequencies match

Code -

solution.c — C

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

bool compareFreq(int freq1[], int freq2[]) {
    for (int i = 0; i < 26; i++) {
        if (freq1[i] != freq2[i]) return false;
    }
    return true;
}

void getCharCount(char* str, int freq[]) {
    memset(freq, 0, 26 * sizeof(int));
    for (int i = 0; str[i]; i++) {
        freq[str[i] - 'a']++;
    }
}

bool solution(char* s1, char* s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    
    if (len1 > len2) return false;
    
    int s1Freq[26];
    getCharCount(s1, s1Freq);
    
    for (int i = 0; i <= len2 - len1; i++) {
        char substring[len1 + 1];
        strncpy(substring, s2 + i, len1);
        substring[len1] = '\0';
        
        int subFreq[26];
        getCharCount(substring, subFreq);
        
        if (compareFreq(s1Freq, subFreq)) {
            return true;
        }
    }
    
    return false;
}

int main() {
    char s1[1001], s2[10001];
    fgets(s1, sizeof(s1), stdin);
    fgets(s2, sizeof(s2), stdin);
    
    s1[strcspn(s1, "\n")] = 0;
    s2[strcspn(s2, "\n")] = 0;
    
    bool result = solution(s1, s2);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

For each of m-n+1 substrings, count n characters

✓ Linear Growth

Space Complexity

O(1)

Only storing character frequency counts (at most 26 letters)

✓ Linear Space

89.0K Views

High Frequency

~25 min Avg. Time

2.2K 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

Frequency Count - Check All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler