Permutation in String

Master this topic with zero to advance depth.

Permutation in String

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

Visual Representation

s1 = "ab", s2 = "eidbaooo"

Target Count: {a:1, b:1}

[e, i] d b a o o o   Count: {e:1, i:1} (Mismatch)
 e [i, d] b a o o o   Count: {i:1, d:1} (Mismatch)
 e i [d, b] a o o o   Count: {d:1, b:1} (Mismatch)
 e i d [b, a] o o o   Count: {b:1, a:1} (Matches!)

Medium

Examples

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
s2 contains one permutation of s1 ("ba").

Approach 1

Level I: Brute Force

Intuition

To check if s2 contains a permutation of s1, we can generate all substrings of s2 that have the same length as s1, and then check if that substring is a permutation of s1 (by sorting both and comparing).

Thought Process

Iterate through all substrings of s2 with length equal to s1.length().
For each substring, sort its characters and also sort the characters of s1.
If the sorted strings match, then a permutation exists.

⏱ O(N * M log M) where N is length of s2 and M is length of s1.💾 O(M)

Detailed Dry Run

Window in s2	Sorted Window	Sorted s1 (ab)	Match?
"ei"	"ei"	"ab"	No
"id"	"di"	"ab"	No
"db"	"bd"	"ab"	No
"ba"	"ab"	"ab"	YES

java

import java.util.*;

public class Main {
    public static boolean checkInclusion(String s1, String s2) {
        int n1 = s1.length(), n2 = s2.length();
        if (n1 > n2) return false;

        char[] s1Chars = s1.toCharArray();
        Arrays.sort(s1Chars);
        String sortedS1 = new String(s1Chars);

        for (int i = 0; i <= n2 - n1; i++) {
            String sub = s2.substring(i, i + n1);
            char[] subChars = sub.toCharArray();
            Arrays.sort(subChars);
            if (new String(subChars).equals(sortedS1)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(checkInclusion("ab", "eidbaooo")); // true
        System.out.println(checkInclusion("ab", "eidboaoo")); // false
    }
}

Approach 2

Level II: Frequency Counter (O(N * 26))

Intuition

Instead of sorting, we can compare character frequency maps. This is still a 'sliding' concept but we re-build or re-check the entire map of size 26 for each window. Since the alphabet size is constant (26), this is technically O(N * 26).

Thought Process

Count frequencies of characters in s1.
Iterate through s2 and for every window of size s1.length(), build a new frequency map.
Compare the window's map with s1's map.

Pattern: Frequency Hashing

⏱ O(N * 26) where N is length of s2.💾 O(26) for the frequency array.

java

public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n1 = s1.length(), n2 = s2.length();
        if (n1 > n2) return false;
        int[] s1Count = new int[26];
        for (char c : s1.toCharArray()) s1Count[c - 'a']++;

        for (int i = 0; i <= n2 - n1; i++) {
            int[] s2Count = new int[26];
            for (int j = i; j < i + n1; j++) s2Count[s2.charAt(j) - 'a']++;
            if (java.util.Arrays.equals(s1Count, s2Count)) return true;
        }
        return false;
    }
}

Approach 3

Level III: Optimal (Sliding Window)

Intuition

Categorization

This is a Fixed Size Window problem because any permutation of s1 must have exactly the same length as s1.

Thought Process

Instead of sorting every substring, we use character frequency counts. A permutation of s1 will have the exact same character frequency count as s1. We maintain a window of size s1.length() in s2 and update the counts as we slide.

Mandatory Variables

left: Marks the start of the window.
s1Counts: Frequency map of characters in s1.
windowCounts: Frequency map of characters in the current s2 window.

⏱ O(N) where N is length of s2.💾 O(1) - alphabet size (26).

Detailed Dry Run

Window	s2 Fragment	Counts Match?	Action
[0, 1]	"ei"	No	Expand R, Shrink L
[1, 2]	"id"	No	Expand R, Shrink L
[2, 3]	"db"	No	Expand R, Shrink L
[3, 4]	"ba"	YES!	Return True

java

import java.util.*;

public class Main {
    public static boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        
        int[] s1Counts = new int[26];
        int[] windowCounts = new int[26];
        
        // Fill counts for s1 and initial window of s2
        for (int i = 0; i < s1.length(); i++) {
            s1Counts[s1.charAt(i) - 'a']++;
            windowCounts[s2.charAt(i) - 'a']++;
        }

        // Comparison helper
        for (int i = 0; i < s2.length() - s1.length(); i++) {
            if (Arrays.equals(s1Counts, windowCounts)) return true;
            
            // Slide window: remove left, add right
            windowCounts[s2.charAt(i) - 'a']--;
            windowCounts[s2.charAt(i + s1.length()) - 'a']++;
        }
        
        return Arrays.equals(s1Counts, windowCounts);
    }

    public static void main(String[] args) {
        System.out.println(checkInclusion("ab", "eidbaooo")); // true
    }
}

⚠️ Common Pitfalls & Tips

Be careful to check the final window after the loop ends, as the last comparison might not happen inside the loop depending on how you structure it.

← Previous QuestionLongest Substring Without Repeating Characters

Next Question →Minimum Window Substring

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.