Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. A permutation of s1 is any string with the same letter counts.
  2. 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");
    }
}

Solve Permutation in String online · All practice problems