567. Permutation in String (Medium)

Problem

Given two strings s1 and s2, return true if s2 contains any permutation of s1 as a substring.

Example

• s1 = "ab", s2 = "eidbaooo" → true ("ba")
• s1 = "ab", s2 = "eidboaoo" → false

LeetCode 567 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, generate all permutations of s1

Generate every permutation of s1 and check whether any is a substring of s2.

Python

from itertools import permutations

def check_inclusion(s1: str, s2: str) -> bool:
    for p in permutations(s1):           # L1: n! permutations generated
        if "".join(p) in s2:            # L2: O(n) join + O(m) substring search
            return True
    return False

TypeScript

function checkInclusion(s1: string, s2: string): boolean {
    function* perms(arr: string[]): Generator<string[]> {   // L1: n! permutations
        if (arr.length <= 1) { yield arr; return; }
        for (let i = 0; i < arr.length; i++) {
            const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
            for (const p of perms(rest)) yield [arr[i], ...p];
        }
    }
    for (const p of perms([...s1])) {
        if (s2.includes(p.join(''))) return true;           // L2: O(n) join + O(m) search
    }
    return false;
}

Go

func checkInclusion(s1 string, s2 string) bool {
  var perms func(arr []byte) [][]byte
  perms = func(arr []byte) [][]byte {                    // L1: n! permutations
    if len(arr) <= 1 {
      return [][]byte{arr}
    }
    var result [][]byte
    for i, ch := range arr {
      rest := append(append([]byte{}, arr[:i]...), arr[i+1:]...)
      for _, p := range perms(rest) {
        result = append(result, append([]byte{ch}, p...))
      }
    }
    return result
  }
  for _, p := range perms([]byte(s1)) {
    if strings.Contains(s2, string(p)) {               // L2: O(n) join + O(m) search
      return true
    }
  }
  return false
}

Swift

final class Solution {
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        var permutations: Set<String> = []
        let characters = Array(s1)
        var used = Array(repeating: false, count: characters.count), current: [Character] = []
        func generate() {
            if current.count == characters.count { permutations.insert(String(current)); return }
            for index in characters.indices where !used[index] {
                used[index] = true; current.append(characters[index]); generate(); current.removeLast(); used[index] = false
            }
        }
        generate()
        return permutations.contains { s2.contains($0) }
    }
}

Where the time goes, line by line

Variables: n = len(s1), m = len(s2).

Line	Per-call cost	Times executed	Contribution
L1 (permutations)	$O(n)$	n!	$O(n! · n)$ ← dominates
L2 (join + in)	$O(n + m)$	up to n!	$O(n! · (n + m)$)

n! grows faster than any polynomial. For n = 10 (len(s1) = 10), that’s 3.6 million permutations; for n = 12, over 479 million.

Complexity

• Time: $O(n! · m)$ where n = len(s1), m = len(s2). Effectively unusable for n > 10.
• Space: $O(n)$ per permutation.

Included to emphasize “permutation substring = anagram substring”, don’t actually enumerate permutations.

Approach 2: Check each window of length n for anagram

Slide a window of size len(s1) across s2; for each position, check whether the window is an anagram of s1 using a Counter comparison.

Python

from collections import Counter

def check_inclusion(s1: str, s2: str) -> bool:
    n, m = len(s1), len(s2)
    if n > m:
        return False
    target = Counter(s1)                          # L1: O(n)
    for i in range(n, m + 1):                     # L2: m - n + 1 windows
        if Counter(s2[i - n:i]) == target:        # L3: O(n) slice + Counter; O(k) compare
            return True
    return False

TypeScript

function checkInclusion(s1: string, s2: string): boolean {
    const n = s1.length, m = s2.length;
    if (n > m) return false;
    const target = new Map<string, number>();
    for (const ch of s1) target.set(ch, (target.get(ch) ?? 0) + 1);  // L1: O(n)
    const mapsEqual = (a: Map<string, number>, b: Map<string, number>) => {
        if (a.size !== b.size) return false;
        for (const [k, v] of a) if (b.get(k) !== v) return false;
        return true;
    };
    for (let i = n; i <= m; i++) {                                     // L2: m-n+1 windows
        const window = new Map<string, number>();
        for (const ch of s2.slice(i - n, i))                          // L3: O(n) Counter
            window.set(ch, (window.get(ch) ?? 0) + 1);
        if (mapsEqual(window, target)) return true;
    }
    return false;
}

Go

func checkInclusion(s1 string, s2 string) bool {
  n, m := len(s1), len(s2)
  if n > m {
    return false
  }
  target := make(map[byte]int)
  for i := 0; i < n; i++ {
    target[s1[i]]++                                   // L1: O(n)
  }
  mapsEqual := func(a, b map[byte]int) bool {
    if len(a) != len(b) {
      return false
    }
    for k, v := range a {
      if b[k] != v {
        return false
      }
    }
    return true
  }
  for i := n; i <= m; i++ {                            // L2: m-n+1 windows
    window := make(map[byte]int)
    for j := i - n; j < i; j++ {                    // L3: O(n) Counter
      window[s2[j]]++
    }
    if mapsEqual(window, target) {
      return true
    }
  }
  return false
}

Swift

final class Solution {
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        let pattern = Array(s1), text = Array(s2)
        guard pattern.count <= text.count else { return false }
        let required = frequencies(pattern)
        for start in 0...(text.count - pattern.count) {
            if frequencies(Array(text[start..<(start + pattern.count)])) == required { return true }
        }
        return false
    }

    private func frequencies(_ values: [Character]) -> [Character: Int] {
        values.reduce(into: [:]) { $0[$1, default: 0] += 1 }
    }
}

Where the time goes, line by line

Variables: n = len(s1), m = len(s2).

Line	Per-call cost	Times executed	Contribution
L1 (Counter s1)	$O(n)$	1	$O(n)$
L2 (loop)	$O(1)$	m - n + 1	$O(m)$
L3 (Counter + compare)	$O(n)$	m - n + 1	$O(m · n)$ ← dominates

For every window position we build a brand-new Counter from a slice, which scans n characters. No sharing across adjacent windows.

Complexity

• Time: $O(m · n)$, driven by L3 (Counter build on every window).
• Space: $O(n)$.

Approach 3: Fixed-size sliding window with running frequency (optimal)

Maintain a single running Counter over the current window. On each slide, increment the new character and decrement the old one. Compare counters in $O(26)$ each step.

Python

from collections import Counter

def check_inclusion(s1: str, s2: str) -> bool:
    n, m = len(s1), len(s2)
    if n > m:
        return False
    target = Counter(s1)                    # L1: O(n)
    window = Counter(s2[:n])               # L2: O(n) initial window
    if window == target:                   # L3: O(k) compare
        return True
    for i in range(n, m):                  # L4: slide m - n steps
        window[s2[i]] += 1                 # L5: O(1) add new char
        window[s2[i - n]] -= 1            # L6: O(1) remove old char
        if window[s2[i - n]] == 0:
            del window[s2[i - n]]          # L7: O(1) cleanup
        if window == target:               # L8: O(k) compare
            return True
    return False

TypeScript

function checkInclusion(s1: string, s2: string): boolean {
    const n = s1.length, m = s2.length;
    if (n > m) return false;
    const target = new Map<string, number>();           // L1: O(n)
    for (const ch of s1) target.set(ch, (target.get(ch) ?? 0) + 1);
    const window = new Map<string, number>();           // L2: O(n) initial window
    for (let i = 0; i < n; i++) {
        const ch = s2[i];
        window.set(ch, (window.get(ch) ?? 0) + 1);
    }
    const mapsEqual = (a: Map<string, number>, b: Map<string, number>) => {
        if (a.size !== b.size) return false;
        for (const [k, v] of a) if (b.get(k) !== v) return false;
        return true;
    };
    if (mapsEqual(window, target)) return true;        // L3: O(k) compare
    for (let i = n; i < m; i++) {                      // L4: slide m - n steps
        window.set(s2[i], (window.get(s2[i]) ?? 0) + 1);       // L5: O(1) add new char
        const outCh = s2[i - n];
        window.set(outCh, window.get(outCh)! - 1);              // L6: O(1) remove old char
        if (window.get(outCh) === 0) window.delete(outCh);      // L7: O(1) cleanup
        if (mapsEqual(window, target)) return true;             // L8: O(k) compare
    }
    return false;
}

Go

func checkInclusion(s1 string, s2 string) bool {
  n, m := len(s1), len(s2)
  if n > m {
    return false
  }
  target := make(map[byte]int)                         // L1: O(n)
  for i := 0; i < n; i++ {
    target[s1[i]]++
  }
  window := make(map[byte]int)                         // L2: O(n) initial window
  for i := 0; i < n; i++ {
    window[s2[i]]++
  }
  mapsEqual := func(a, b map[byte]int) bool {
    if len(a) != len(b) {
      return false
    }
    for k, v := range a {
      if b[k] != v {
        return false
      }
    }
    return true
  }
  if mapsEqual(window, target) {                       // L3: O(k) compare
    return true
  }
  for i := n; i < m; i++ {                            // L4: slide m - n steps
    window[s2[i]]++                                  // L5: O(1) add new char
    outCh := s2[i-n]
    window[outCh]--                                  // L6: O(1) remove old char
    if window[outCh] == 0 {
      delete(window, outCh)                        // L7: O(1) cleanup
    }
    if mapsEqual(window, target) {                   // L8: O(k) compare
      return true
    }
  }
  return false
}

Swift

final class Solution {
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        let pattern = Array(s1), text = Array(s2)
        guard pattern.count <= text.count else { return false }
        let required = pattern.reduce(into: [Character: Int]()) { $0[$1, default: 0] += 1 }
        var window: [Character: Int] = [:], satisfied = 0
        for right in text.indices {
            let added = text[right]
            window[added, default: 0] += 1
            if window[added] == required[added] { satisfied += 1 }
            if right >= pattern.count {
                let removed = text[right - pattern.count]
                if window[removed] == required[removed] { satisfied -= 1 }
                window[removed, default: 0] -= 1
            }
            if right >= pattern.count - 1 && satisfied == required.count { return true }
        }
        return false
    }
}

Where the time goes, line by line

Variables: n = len(s1), m = len(s2), k = number of distinct characters in s1 (≤ 26).

Line	Per-call cost	Times executed	Contribution
L1/L2 (init)	$O(n)$	1	$O(n)$
L3 (initial check)	$O(k)$	1	$O(k)$
L4 (slide loop)	$O(1)$ body	m - n	$O(m)$ ← dominates
L5/L6/L7 (update window)	$O(1)$	m - n	$O(m)$
L8 (compare)	$O(k)$	m - n	$O(m · k)$ = $O(m)$ since k ≤ 26

Instead of rebuilding the Counter each step, we do two $O(1)$ updates (L5/L6) and one $O(k)$ comparison (L8). Since k ≤ 26, L8 is effectively $O(1)$, making the total $O(m)$.

Complexity

• Time: $O(m)$, driven by L4/L8 (single pass with $O(1)$ window updates and $O(26)$ comparison).
• Space: $O(k)$.

Even tighter: matching counter with “matches” counter

Instead of comparing full counters every step, maintain a matches integer that counts how many characters in the alphabet have the correct count. Increment/decrement matches when a character’s running count crosses its target. Check matches == 26 each step. Same $O(m)$, smaller constant factor.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Enumerate permutations	$O(n! · m)$	$O(n)$
Per-window Counter	$O(m · n)$	$O(n)$
Running counter window	$O(m)$	$O(k)$

The key realization is “permutation substring = anagram substring”; once you see it, the fixed-size sliding window falls out.

Test cases

Python

# Quick smoke tests - paste into a REPL or save as test_567.py and run.
# Uses the optimal Approach 3 implementation.

from collections import Counter

def check_inclusion(s1: str, s2: str) -> bool:
    n, m = len(s1), len(s2)
    if n > m:
        return False
    target = Counter(s1)
    window = Counter(s2[:n])
    if window == target:
        return True
    for i in range(n, m):
        window[s2[i]] += 1
        window[s2[i - n]] -= 1
        if window[s2[i - n]] == 0:
            del window[s2[i - n]]
        if window == target:
            return True
    return False

def _run_tests():
    assert check_inclusion("ab", "eidbaooo") == True    # "ba" at index 3
    assert check_inclusion("ab", "eidboaoo") == False
    assert check_inclusion("a", "a") == True            # single char match
    assert check_inclusion("a", "b") == False           # single char no match
    assert check_inclusion("abc", "ab") == False        # s1 longer than s2
    assert check_inclusion("aab", "aabc") == True       # "aab" is a permutation match
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function checkInclusion(s1: string, s2: string): boolean {
    const n = s1.length, m = s2.length;
    if (n > m) return false;
    const target = new Map<string, number>();
    for (const ch of s1) target.set(ch, (target.get(ch) ?? 0) + 1);
    const window = new Map<string, number>();
    for (let i = 0; i < n; i++) {
        const ch = s2[i];
        window.set(ch, (window.get(ch) ?? 0) + 1);
    }
    const mapsEqual = (a: Map<string, number>, b: Map<string, number>) => {
        if (a.size !== b.size) return false;
        for (const [k, v] of a) if (b.get(k) !== v) return false;
        return true;
    };
    if (mapsEqual(window, target)) return true;
    for (let i = n; i < m; i++) {
        window.set(s2[i], (window.get(s2[i]) ?? 0) + 1);
        const outCh = s2[i - n];
        window.set(outCh, window.get(outCh)! - 1);
        if (window.get(outCh) === 0) window.delete(outCh);
        if (mapsEqual(window, target)) return true;
    }
    return false;
}

console.assert(checkInclusion("ab", "eidbaooo") === true);
console.assert(checkInclusion("ab", "eidboaoo") === false);
console.assert(checkInclusion("a", "a") === true);
console.assert(checkInclusion("a", "b") === false);
console.assert(checkInclusion("abc", "ab") === false);
console.assert(checkInclusion("aab", "aabc") === true);
console.log("all tests pass");

Go

func checkInclusion(s1 string, s2 string) bool {
  n, m := len(s1), len(s2)
  if n > m {
    return false
  }
  target := make(map[byte]int)
  for i := 0; i < n; i++ {
    target[s1[i]]++
  }
  window := make(map[byte]int)
  for i := 0; i < n; i++ {
    window[s2[i]]++
  }
  mapsEqual := func(a, b map[byte]int) bool {
    if len(a) != len(b) {
      return false
    }
    for k, v := range a {
      if b[k] != v {
        return false
      }
    }
    return true
  }
  if mapsEqual(window, target) {
    return true
  }
  for i := n; i < m; i++ {
    window[s2[i]]++
    outCh := s2[i-n]
    window[outCh]--
    if window[outCh] == 0 {
      delete(window, outCh)
    }
    if mapsEqual(window, target) {
      return true
    }
  }
  return false
}

Related data structures

• Strings, input; substring == character sequence
• Hash Tables, frequency counters over s1 and the running window

Related concepts

• Sliding Window, the contiguous range invariant behind expanding and shrinking a window.
• Hash Map Counting, the lookup table pattern for complements, frequencies, and seen items.