567. Permutation in String
Permutation in String (LeetCode 567) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Character Frequency Matching subpattern.
How to solve Permutation in String
Permutation in String is a Character Frequency Matching Window problem, part of Sliding Window. Learn sliding window with character frequency matching for anagram and permutation substring problems.
Work towards the solution in these steps:
- Obviously, brute force will result in TLE. Think of something else.
- How will you check whether one string is a permutation of another string?
- One way is to sort the string and then compare. But, Is there a better way?
The reference solution runs in O(m) time and O(1) space.
The Permutation in String solution and editorial walks through the full approach with reference code.
Problem statement
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 <= 104
- s1 and s2 consist of lowercase English letters.
Topics and companies
Topics: Hash Table, Two Pointers, String, Sliding Window.
Reported in interviews at Adobe, Amazon, Bloomberg, Facebook, Google, Microsoft, Yandex.
How to practise Permutation in String on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m) time and O(1) space.
Open Permutation in String in the code editor, or read the Permutation in String editorial for a worked solution with its approach and complexity analysis.
Where Permutation in String sits in the DSA pattern sheet
Problems related to Permutation in String
Other problems that use the same Character Frequency Matching and Sliding Window techniques:
- Find All Anagrams in a String — Medium, same subpattern
- Calculate Compressed Mean — Easy, same pattern
- Contains Duplicate II — Easy, same pattern
- Continuous Subarrays — Medium, same pattern
- Find Longest Special Substring That Occurs Thrice I — Medium, same pattern
- Find the Power of K-Size Subarrays I — Medium, same pattern
Permutation in String FAQ
What is the LeetCode number of Permutation in String?
Permutation in String is LeetCode problem 567, rated Medium.
What pattern is used to solve Permutation in String?
Permutation in String is a Character Frequency Matching Window problem. It belongs to the Sliding Window pattern, in the Character Frequency Matching subpattern.
What is the time complexity of Permutation in String?
The reference solution runs in O(m) time and O(1) space.
Which companies ask Permutation in String?
Permutation in String has been reported in interviews at Adobe, Amazon, Bloomberg, Facebook, Google, Microsoft, Yandex.