Loading problem...
Given two strings text and pattern, your task is to identify all starting positions within text where a rearrangement (permutation) of pattern appears as a contiguous substring.
A permutation of a string is any rearrangement of its characters. For example, "abc" has the following permutations: "abc", "acb", "bac", "bca", "cab", and "cba". Two strings are considered permutations of each other if and only if they contain exactly the same characters with exactly the same frequencies.
You need to scan through the text string and find every position where a window of length equal to pattern contains exactly the same character distribution as pattern itself. This means the substring starting at that position is one of the many possible permutations of pattern.
Return an array containing all such starting indices. The indices in the result may be returned in any order.
text = "cbaebabacd"
pattern = "abc"[0,6]The substring starting at index 0 is "cba", which is a permutation of "abc" (contains exact same characters: a, b, c). The substring starting at index 6 is "bac", which is also a permutation of "abc". No other windows of length 3 contain exactly the characters a, b, and c.
text = "abab"
pattern = "ab"[0,1,2]At index 0, we have "ab" which matches the pattern directly. At index 1, we have "ba" which is a permutation of "ab". At index 2, we have "ab" again. Since all three positions contain valid permutations of the pattern, all three indices are returned.
text = "hello"
pattern = "xyz"[]The pattern "xyz" contains characters x, y, and z, none of which appear in the text "hello". Therefore, no permutation of the pattern can exist anywhere in the text, and we return an empty array.
Constraints