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.

Description Hints 6 Solution Video 19:40

567. Permutation in String

Medium49.8% acceptance16 companies

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 <= 10⁴
s1 and s2 consist of lowercase English letters.

Asked at 16 companies

VK Walmart Labs Yandex

TCS Amazon Microsoft Adobe Databricks

Google Meta Bloomberg Tiktok

+4 more

Oracle Apple

Cisco Salesforce

Topics

Hints open one at a time

Hint 1

Obviously, brute force will result in TLE. Think of something else.

Hint 2

How will you check whether one string is a permutation of another string?

Hint 3

One way is to sort the string and then compare. But, Is there a better way?

Hint 4

If one string is a permutation of another string then they must have one common metric. What is that?

Hint 5

Both strings must have same character frequencies, if one is permutation of another. Which data structure should be used to store frequencies?

Hint 6

What about hash table? An array of size 26?

19:40

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution