Given two strings, s1 and s2, determine whether any permutation of s1 appears as a contiguous substring within s2. In other words, return TRUE if s2 contains a substring that uses the same characters as s1, with the same frequencies, but possibly in a different order. Otherwise, FALSE.
A permutation of a string is any possible arrangement of all its characters. For example, for the string “ab”, the permutations are: “ab” and “ba”.
Constraints:
s1.length, s2.length
s1 and s2 consist of lowercase English letters.
A naive approach would be to generate all possible rearrangements of s1 and check whether any appear in s2. But that would quickly become inefficient for longer strings, because the number of permutations grows extremely fast. For a three-letter string like "abc", there are already six permutations; for "abcdef", there are hundreds. So, instead of trying to rearrange s1, we look for an efficient alternative.
Two strings are permutations of each other if and only if they contain the same characters the same number of times. For example, "abc" and "bca" are permutations because both have one a, one b, and one c. This means that if we find any substring of s2 that is the same length as s1 and has the same character counts, then that substring must be a permutation of s1.
Quick recall
A substring is a contiguous sequence of characters within a larger string. So, if s1 = "ab" and s2 = "acb", even though both strings contain the same counts of letters a and b, there’s no two-letter block in s2 that contains both together so that the result would be FALSE.
The same idea is used in this solution, keeping track of the character counts of s1 inside s2. To do this efficiently, the algorithm uses a sliding window over s2. At any given moment, this window represents a substring of s2 that’s the same length as s1 and could potentially be one of its permutations. To check that, compare the frequency of each character in s1 with the frequency of the characters inside this window.
If the counts match, it means the current window contains the same letters as s1, just possibly in a different order, so a valid permutation is found. In that case, return TRUE. If the counts don’t match, and there are still characters left to examine in s2, slide the window forward by one character. That means one new character from the right side of s2 is added to the window, and one old character from the left side is removed. This is important because the window must always stay the same length as s1. Keep doing this until either a match is found or the end of s2 is reached. If all possible windows have been checked and none match the character frequencies of s1, then return FALSE.
Let's look at the algorithm steps:
Store the lengths of s1 and s2 in n1 and n2.
If n1
Given two strings, s1 and s2, determine whether any permutation of s1 appears as a contiguous substring within s2. In other words, return TRUE if s2 contains a substring that uses the same characters as s1, with the same frequencies, but possibly in a different order. Otherwise, FALSE.
A permutation of a string is any possible arrangement of all its characters. For example, for the string “ab”, the permutations are: “ab” and “ba”.
Constraints:
s1.length, s2.length
s1 and s2 consist of lowercase English letters.
A naive approach would be to generate all possible rearrangements of s1 and check whether any appear in s2. But that would quickly become inefficient for longer strings, because the number of permutations grows extremely fast. For a three-letter string like "abc", there are already six permutations; for "abcdef", there are hundreds. So, instead of trying to rearrange s1, we look for an efficient alternative.
Two strings are permutations of each other if and only if they contain the same characters the same number of times. For example, "abc" and "bca" are permutations because both have one a, one b, and one c. This means that if we find any substring of s2 that is the same length as s1 and has the same character counts, then that substring must be a permutation of s1.
Quick recall
A substring is a contiguous sequence of characters within a larger string. So, if s1 = "ab" and s2 = "acb", even though both strings contain the same counts of letters a and b, there’s no two-letter block in s2 that contains both together so that the result would be FALSE.
The same idea is used in this solution, keeping track of the character counts of s1 inside s2. To do this efficiently, the algorithm uses a sliding window over s2. At any given moment, this window represents a substring of s2 that’s the same length as s1 and could potentially be one of its permutations. To check that, compare the frequency of each character in s1 with the frequency of the characters inside this window.
If the counts match, it means the current window contains the same letters as s1, just possibly in a different order, so a valid permutation is found. In that case, return TRUE. If the counts don’t match, and there are still characters left to examine in s2, slide the window forward by one character. That means one new character from the right side of s2 is added to the window, and one old character from the left side is removed. This is important because the window must always stay the same length as s1. Keep doing this until either a match is found or the end of s2 is reached. If all possible windows have been checked and none match the character frequencies of s1, then return FALSE.
Let's look at the algorithm steps:
Store the lengths of s1 and s2 in n1 and n2.
If n1