Permutation in String solution and explanation
TCS
Google
Cisco
9 more videos on this problem
Permutation in String - Leetcode 567 - PythonNeetCode · 19:40 · 380K views
Permutation in String | Leetcode #567 | Anagram of string s1 in string s2Techdose · 7:28 · 77K views
Permutation in String - Leetcode 567 - Fixed Sliding Window (Python)Greg Hogg · 14:23 · 32K views
Permutation in String | Multiple Approaches | Clean Dry Run | Leetcode 567 | codestorywithMIKcodestorywithMIK · 22:19 · 23K views
LeetCode 567 | Permutation in String | Solution Explained (Whiteboard + Algorithm in Java)Xavier Elon · 10:29 · 18K views
[Java] Leetcode 567. Permutation in String [Sliding Window #7]Eric Programming · 11:13 · 8K views
Permutation in String - LeetCode #567 with python programmingCodingNinja · 12:27 · 6K views
Permutation in String | LeetCode 567Destination FAANG · 13:02 · 2K views
567. Permutation in string #LeetcodeSolutionsLeetCode Solutions · 6:07 · 1K views
567. Permutation in String | LeetCodeDeep Tech · 12:20 · 791 views
The 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.
Example 1:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input: s1 = "ab", s2 = "eidboaoo" Output: false
Constraints:
1 <= s1.length, s2.length <= 104s1ands2consist of lowercase English letters.
Approach overview
Problem Overview: Given two strings s1 and s2, determine whether any permutation of s1 appears as a substring inside s2. In practice, you need to detect whether some contiguous window of s2 contains exactly the same character counts as s1.
Approach 1: Brute Force Permutation Check (O(n * m!) time, O(m) space)
The naive solution generates every permutation of s1 and checks whether it exists in s2. For a string of length m, there are m! permutations, and each one requires a substring search in s2. Even with optimizations, this quickly becomes infeasible for typical constraints. This approach is useful only as a conceptual baseline to understand that the problem is essentially about matching character frequencies rather than exact order.
Approach 2: Sliding Window with Frequency Count (O(n) time, O(1) space)
The optimal solution treats the problem as a fixed-size window comparison. First compute a frequency count for characters in s1. Then iterate through s2 using a window of length s1.length(). For each step, update the frequency of the entering character and remove the frequency of the exiting character. If the frequency arrays match, the current window is a permutation of s1. Because the alphabet is limited (typically 26 lowercase letters), comparing counts is constant time. This technique relies on the sliding window pattern and often pairs with two pointers to maintain the window boundaries efficiently.
Approach 3: Character Mapping Using Hash Map (O(n) time, O(k) space)
This variation replaces the fixed-size array with a hash map that tracks how many characters are still required to match s1. As you expand the window across s2, decrement counts for seen characters. When a count reaches zero, that character requirement is satisfied. If the window grows larger than s1, increment the count of the character leaving the window. When all required characters are satisfied simultaneously, a valid permutation exists. This approach works well when the character set is large or unknown and demonstrates the use of a hash table for dynamic frequency tracking.
Recommended for interviews: Interviewers typically expect the sliding window frequency-count solution. It demonstrates recognition of substring pattern matching and efficient window maintenance in O(n) time. Mentioning the brute force permutation idea shows you understand the underlying requirement, but implementing the optimized window approach proves you can apply common string-processing patterns effectively.
Approach 1: Sliding Window with Frequency Count
The main idea is to use a sliding window technique to compare the character frequency of a substring of s2 with the character frequency of s1. If they match, it means s2 contains a permutation of s1.
- Initialize two frequency arrays for s1 and the sliding window in s2 of the same size.
- Slide the window across s2, updating its frequency count and comparing it with s1's frequency count at each step.
- If the window's frequency array matches s1's frequency array, return true, else continue sliding the window.
- If no match is found by the end of s2, return false.
from collections import Counter
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
count1 = Counter(s1)
count2 = Counter(s2[:len(s1)])
if count1 == count2:
return True
for i in range(len(s1), len(s2)):
count2[s2[i]] += 1
count2[s2[i - len(s1)]] -= 1
if count2[s2[i - len(s1)]] == 0:
del count2[s2[i - len(s1)]]
if count1 == count2:
return True
return Falseimport java.util.Arrays;
public class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
int[] count1 = new int[26];
int[] count2 = new int[26];
for (int i = 0; i < s1.length(); ++i) {
count1[s1.charAt(i) - 'a']++;
count2[s2.charAt(i) - 'a']++;
}
for (int i = s1.length(); i < s2.length(); ++i) {
if (Arrays.equals(count1, count2)) return true;
count2[s2.charAt(i) - 'a']++;
count2[s2.charAt(i - s1.length()) - 'a']--;
}
return Arrays.equals(count1, count2);
}
}#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool checkInclusion(string s1, string s2) {
vector<int> count1(26, 0), count2(26, 0);
int len1 = s1.size(), len2 = s2.size();
if (len1 > len2) return false;
for (int i = 0; i < len1; ++i) {
count1[s1[i] - 'a']++;
count2[s2[i] - 'a']++;
}
for (int i = len1; i < len2; ++i) {
if (count1 == count2) return true;
count2[s2[i] - 'a']++;
count2[s2[i - len1] - 'a']--;
}
return count1 == count2;
}
};var checkInclusion = function(s1, s2) {
if (s1.length > s2.length) return false;
const count1 = new Array(26).fill(0);
const count2 = new Array(26).fill(0);
for (let i = 0; i < s1.length; i++) {
count1[s1.charCodeAt(i) - 97]++;
count2[s2.charCodeAt(i) - 97]++;
}
for (let i = s1.length; i < s2.length; i++) {
if (arraysEqual(count1, count2)) return true;
count2[s2.charCodeAt(i) - 97]++;
count2[s2.charCodeAt(i - s1.length) - 97]--;
}
return arraysEqual(count1, count2);
};
function arraysEqual(a, b) {
for (let i = 0; i < a.length; i++) {
if (a[i] !== b[i]) return false;
}
return true;
}#include <stdbool.h>
#include <string.h>
bool checkInclusion(char * s1, char * s2) {
int len1 = strlen(s1), len2 = strlen(s2);
if (len1 > len2) return false;
int count1[26] = {0}, count2[26] = {0};
for (int i = 0; i < len1; ++i) {
count1[s1[i] - 'a']++;
count2[s2[i] - 'a']++;
}
for (int i = len1; i < len2; ++i) {
if (memcmp(count1, count2, 26 * sizeof(int)) == 0) return true;
count2[s2[i] - 'a']++;
count2[s2[i - len1] - 'a']--;
}
return memcmp(count1, count2, 26 * sizeof(int)) == 0;
}using System;
using System.Linq;
public class Solution {
public bool CheckInclusion(string s1, string s2) {
if (s1.Length > s2.Length) return false;
int[] count1 = new int[26];
int[] count2 = new int[26];
for (int i = 0; i < s1.Length; ++i) {
count1[s1[i] - 'a']++;
count2[s2[i] - 'a']++;
}
for (int i = s1.Length; i < s2.Length; ++i) {
if (count1.SequenceEqual(count2)) return true;
count2[s2[i] - 'a']++;
count2[s2[i - s1.Length] - 'a']--;
}
return count1.SequenceEqual(count2);
}
}This Python solution uses the Counter class to maintain character frequencies. The sliding window is managed by updating the counts incrementally and removing characters with zero count to keep the counter small.
Time Complexity: O(n), where n is the length of s2.
Space Complexity: O(1) if considering 26 characters, though in Python, it's dynamically adjusted based on content.
Approach 2: Character Mapping Using Hash Map
Leverage a hash map (or dictionary) to record the character count of s1 and use it to compare with segments of s2. This approach focuses on incremental updates to the map as the window slides over s2.
- Construct a hash map for s1 storing the frequency of each character.
- Use a sliding window to traverse s2, updating the map for each window section.
- Compare the map for each window with the map of s1 and determine if a permutation is found.
from collections import defaultdict
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
count1 = defaultdict(int)
count2 = defaultdict(int)
for ch in s1:
count1[ch] += 1
for ch in s2[:len(s1)]:
count2[ch] += 1
matches = 0
for key in count1:
if count1[key] == count2[key]:
matches += 1
l = 0
for r in range(len(s1), len(s2)):
if matches == len(count1):
return True
new_char = s2[r]
count2[new_char] += 1
if count2[new_char] == count1[new_char]:
matches += 1
elif count2[new_char] == count1[new_char] + 1:
matches -= 1
old_char = s2[l]
count2[old_char] -= 1
if count2[old_char] == count1[old_char]:
matches += 1
elif count2[old_char] == count1[old_char] - 1:
matches -= 1
l += 1
return matches == len(count1)var checkInclusion = function(s1, s2) {
let len1 = s1.length, len2 = s2.length;
if (len1 > len2) return false;
const count1 = {}, count2 = {};
for (let i = 0; i < len1; i++) {
count1[s1[i]] = (count1[s1[i]] || 0) + 1;
count2[s2[i]] = (count2[s2[i]] || 0) + 1;
}
let matches = 0;
for (let key in count1) {
if (count1[key] === count2[key]) matches++;
}
for (let i = len1; i < len2; i++) {
if (matches === Object.keys(count1).length) return true;
let inChar = s2[i];
count2[inChar] = (count2[inChar] || 0) + 1;
if (count1[inChar] === count2[inChar]) matches++;
else if (count1[inChar] + 1 === count2[inChar]) matches--;
let outChar = s2[i - len1];
count2[outChar]--;
if (count1[outChar] === count2[outChar]) matches++;
else if (count1[outChar] - 1 === count2[outChar]) matches--;
}
return matches === Object.keys(count1).length;
};This Python solution optimizes character comparison by leveraging a hash map to keep track of character frequency changes as the sliding window moves. Instead of full map comparison for each slide, it increments and decrements values while checking conditions, which reduces the overhead of comparing full data structures.
Time Complexity: O(n), where n is the length of s2.
Space Complexity: O(1), since the hash map's size is bounded by the character set size of 26.
Approach 3: Sliding Window
We use an array cnt to record the characters and their counts that need to be matched, and a variable need to record the number of different characters that still need to be matched. Initially, cnt contains the character counts from the string s1, and need is the number of different characters in s1.
Then we traverse the string s2. For each character, we decrement its corresponding value in cnt. If the decremented value equals 0, it means the current character's count in s1 is satisfied, and we decrement need. If the current index i is greater than or equal to the length of s1, we need to increment the corresponding value in cnt for s2[i-s1]. If the incremented value equals 1, it means the current character's count in s1 is no longer satisfied, and we increment need. During the traversal, if the value of need equals 0, it means all character counts are satisfied, and we have found a valid substring, so we return true.
Otherwise, if the traversal ends without finding a valid substring, we return false.
The time complexity is O(m + n), where m and n are the lengths of strings s1 and s2, respectively. The space complexity is O(|\Sigma|), where \Sigma is the character set. In this problem, the character set is lowercase letters, so the space complexity is constant.
function checkInclusion(s1: string, s2: string): boolean {
let need = 0;
const cnt: number[] = Array(26).fill(0);
const a = 'a'.charCodeAt(0);
for (const c of s1) {
if (++cnt[c.charCodeAt(0) - a] === 1) {
need++;
}
}
const [m, n] = [s1.length, s2.length];
for (let i = 0; i < n; i++) {
let c = s2.charCodeAt(i) - a;
if (--cnt[c] === 0) {
need--;
}
if (i >= m) {
c = s2.charCodeAt(i - m) - a;
if (++cnt[c] === 1) {
need++;
}
}
if (need === 0) {
return true;
}
}
return false;
}func checkInclusion(s1 string, s2 string) bool {
need := 0
cnt := [26]int{}
for _, c := range s1 {
if cnt[c-'a']++; cnt[c-'a'] == 1 {
need++
}
}
m, n := len(s1), len(s2)
for i := 0; i < n; i++ {
c := s2[i] - 'a'
if cnt[c]--; cnt[c] == 0 {
need--
}
if i >= m {
c = s2[i-m] - 'a'
if cnt[c]++; cnt[c] == 1 {
need++
}
}
if need == 0 {
return true
}
}
return false
}impl Solution {
pub fn check_inclusion(s1: String, s2: String) -> bool {
let mut need = 0;
let mut cnt = vec![0; 26];
for c in s1.chars() {
let index = (c as u8 - b'a') as usize;
if cnt[index] == 0 {
need += 1;
}
cnt[index] += 1;
}
let m = s1.len();
let n = s2.len();
let s2_bytes = s2.as_bytes();
for i in 0..n {
let c = (s2_bytes[i] - b'a') as usize;
cnt[c] -= 1;
if cnt[c] == 0 {
need -= 1;
}
if i >= m {
let c = (s2_bytes[i - m] - b'a') as usize;
cnt[c] += 1;
if cnt[c] == 1 {
need += 1;
}
}
if need == 0 {
return true;
}
}
false
}
}class Solution {
/**
* @param String $s1
* @param String $s2
* @return Boolean
*/
function checkInclusion($s1, $s2) {
$need = 0;
$cnt = array_fill(0, 26, 0);
for ($i = 0; $i < strlen($s1); $i++) {
$index = ord($s1[$i]) - ord('a');
if (++$cnt[$index] == 1) {
$need++;
}
}
$m = strlen($s1);
$n = strlen($s2);
for ($i = 0; $i < $n; $i++) {
$c = ord($s2[$i]) - ord('a');
if (--$cnt[$c] == 0) {
$need--;
}
if ($i >= $m) {
$c = ord($s2[$i - $m]) - ord('a');
if (++$cnt[$c] == 1) {
$need++;
}
}
if ($need == 0) {
return true;
}
}
return false;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window with Frequency Count | Time Complexity: O(n), where n is the length of s2. |
| Character Mapping Using Hash Map | Time Complexity: O(n), where n is the length of s2. |
| Sliding Window | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutation Generation | O(n * m!) | O(m) | Conceptual baseline for understanding permutations; impractical for real constraints |
| Sliding Window with Frequency Count | O(n) | O(1) | Best general solution when character set is fixed (e.g., lowercase letters) |
| Character Mapping Using Hash Map | O(n) | O(k) | Useful when character set is large or not limited to a small alphabet |
Frequently asked questions
Is Permutation in String easy or hard?
Permutation in String is typically classified as a medium difficulty problem. The logic becomes straightforward once you recognize the sliding window pattern, but identifying the frequency-based optimization can be challenging for beginners.
Permutation in String Python/Java solution
Most Python and Java implementations use a sliding window with a 26-length frequency array. Python solutions often rely on lists for counts, while Java uses int arrays. Both maintain a fixed-size window and update counts as characters enter and leave the window.
How to solve Permutation in String in O(n)?
Use a sliding window of size s1.length() over s2. Maintain a frequency array for s1 and update another array as the window moves. Add the incoming character, remove the outgoing character, and compare counts. Because each character is processed once, the total complexity is O(n).
What is the best approach for Permutation in String?
The most efficient approach uses a sliding window with a frequency count array. You maintain a window of length equal to s1 and track character counts as the window moves across s2. When the frequency of characters in the window matches the frequency of s1, a permutation exists. This method runs in O(n) time with O(1) extra space for a fixed alphabet.
Is Permutation in String asked at Google/Amazon/Meta?
Permutation in String is a common string and sliding window interview question. Variants of this problem have appeared in interviews at companies like Amazon, Google, Meta, and Microsoft because it tests substring matching, frequency counting, and sliding window optimization.
What data structure is used in Permutation in String?
The core data structures are frequency arrays or hash maps that track character counts. These are combined with a sliding window technique implemented using two pointers to efficiently scan the second string.
What is the time complexity of Permutation in String?
The optimal sliding window solution runs in O(n) time where n is the length of s2. Each character enters and leaves the window at most once, and frequency comparisons are constant time when using a fixed-size array for lowercase letters.