How do you solve Permutation in String on LeetCode?

Permutation in String (LeetCode #567) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Character counts can uniquely identify permutations.

What is the brute force solution for Permutation in String?

The brute force approach for Permutation in String is Brute Force, with O(n²) time complexity and O(1) space complexity. We can generate all permutations of s1 and check if any of them exist as a substring in s2. This is straightforward but inefficient due to the high number of permutations. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Permutation in String?

Permutation in String uses the following concepts: Hash Table, Two Pointers, String, Sliding Window. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Permutation in String?

Always mention the brute-force approach first to show understanding. Explain your thought process clearly when transitioning to the optimal solution. Practice implementing both approaches to solidify your understanding.

What are common mistakes when solving Permutation in String?

Not considering edge cases where s1 is longer than s2. Confusing character counts with string comparisons.

#567

Permutation in String

Medium

Hash TableTwo PointersStringSliding WindowHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

Instead of generating all permutations, we can use a sliding window approach with character counts to check if s2 contains a permutation of s1. This is efficient and avoids unnecessary computations.

⚙️

Algorithm

4 steps

1Step 1: Create a frequency count of characters in s1.
2Step 2: Use a sliding window of size equal to s1's length to traverse s2, updating the character count in the window.
3Step 3: Compare the character counts of the current window with s1's character counts. If they match, return true.
4Step 4: If no matching window is found after traversing s2, return false.

solution.py19 lines

1# Full working Python code
2from collections import Counter
3
4def checkInclusion(s1, s2):
5    len_s1, len_s2 = len(s1), len(s2)
6    if len_s1 > len_s2:
7        return False
8    count_s1 = Counter(s1)
9    count_window = Counter(s2[:len_s1])
10    if count_s1 == count_window:
11        return True
12    for i in range(len_s1, len_s2):
13        count_window[s2[i]] += 1
14        count_window[s2[i - len_s1]] -= 1
15        if count_window[s2[i - len_s1]] == 0:
16            del count_window[s2[i - len_s1]]
17        if count_s1 == count_window:
18            return True
19    return False

ℹ

Complexity note: The time complexity is O(n) because we traverse s2 once, and the space complexity is O(1) since we only use fixed-size arrays for character counts.

1Character counts can uniquely identify permutations.
2Using a sliding window reduces unnecessary checks.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.