Practice › Sliding Window
Permutation in String
Medium · Sliding Window · Asked at Microsoft, Amazon, Google, Oracle
Print YES if s2 contains a permutation of s1 as a contiguous substring (some substring of s2 is an anagram of s1), otherwise NO.
Input
First line: s1. Second line: s2. Both are lowercase.
Output
YES or NO.
Constraints
- 1 ≤ |s1|, |s2| ≤ 10^5
Slide a window of length |s1| over s2 and keep letter counts; compare the 26 counts (or track how many letters match).
Example 1
Input
ab eidbaooo
Output
YES
Example 2
Input
ab eidboaoo
Output
NO
Hints
- A permutation of s1 is any string with the same letter counts.
- Slide a window of length |s1| across s2, updating 26 counts as one letter enters and one leaves, and compare with the counts of s1.
Approach
Build the count array of s1. Keep a count array for the current window of s2 with length |s1|: add the new right letter, remove the letter that falls off the left. After each step compare the two arrays (26 comparisons). If |s1| > |s2| the answer is immediately NO.
Complexity: O(26 · |s2|) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string a, b;
cin >> a >> b;
int m = a.size(), n = b.size();
if (m > n) {
cout << "NO\n";
return 0;
}
vector<int> need(26, 0), have(26, 0);
for (char c : a) need[c - 'a']++;
for (int i = 0; i < n; i++) {
have[b[i] - 'a']++;
if (i >= m) have[b[i - m] - 'a']--;
if (i >= m - 1 && have == need) {
cout << "YES\n";
return 0;
}
}
cout << "NO\n";
return 0;
}Python solution
import sys
a, b = sys.stdin.read().split()[:2]
m, n = len(a), len(b)
need, have = [0] * 26, [0] * 26
for c in a:
need[ord(c) - 97] += 1
ans = "NO"
for i in range(n):
have[ord(b[i]) - 97] += 1
if i >= m:
have[ord(b[i - m]) - 97] -= 1
if i >= m - 1 and have == need:
ans = "YES"
break
print(ans)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String a = sc.next(), b = sc.next();
int m = a.length(), n = b.length();
int[] need = new int[26], have = new int[26];
for (char c : a.toCharArray()) need[c - 'a']++;
for (int i = 0; i < n; i++) {
have[b.charAt(i) - 'a']++;
if (i >= m) have[b.charAt(i - m) - 'a']--;
if (i >= m - 1 && Arrays.equals(have, need)) {
System.out.println("YES");
return;
}
}
System.out.println("NO");
}
}