159. Shuffled Inside
A puzzle setter takes a word s1, shuffles its letters into any order, and then hides the shuffled copy inside a longer string s2 as one unbroken block of letters. A solver must tell whether such a hidden block exists.
Return true if s2 contains a substring that is a permutation of s1, meaning a substring of the same length with exactly the same letters, each appearing the same number of times, in any order. Otherwise return false. The block must be contiguous in s2, and s1 itself counts as one of its own permutations.
Example 1
- Input:
- s1 = "abc", s2 = "dcbaef"
- Output:
- true
- Explanation:
The substring cba of s2 uses exactly the letters a, b and c, so it is a permutation of abc and the answer is true.
Example 2
- Input:
- s1 = "ab", s2 = "acbd"
- Output:
- false
- Explanation:
The substrings of length 2 are ac, cb and bd. None of them is made of exactly one a and one b, so the answer is false.
Example 3
- Input:
- s1 = "aab", s2 = "abab"
- Output:
- true
- Explanation:
The substring aba (positions 0 to 2) has two a and one b, matching aab, so the answer is true.
Constraints
1 ≤ s1.length, s2.length ≤ 105
s1 and s2 consist of lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)