DSA problem
Permutation in String
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.
A permutation of s1 is any rearrangement of its characters, so every permutation has the exact same length as s1 and the exact same character-frequency counts. Therefore the task reduces to checking whether any substring of s2 of length len(s1) has a frequency table identical to that of s1. A fixed-size sliding window over s2 solves this in linear time.
Examples
Example 1
Input:
s1 = "ab", s2 = "eidbaooo"Output:
trueExplanation: s2 contains the substring "ba" (indices 3-4), which is a permutation of "ab".
Example 2
Input:
s1 = "ab", s2 = "eidboaoo"Output:
falseExplanation: No substring of "eidboaoo" of length 2 is a permutation of "ab".
Example 3
Input:
s1 = "adc", s2 = "dcda"Output:
trueExplanation: The substring "dcd" is not a match, but "cda" (indices 1-3) is a permutation of "adc".
Constraints
- 1 <= s1.length, s2.length <= 10^4
- s1 and s2 consist of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.