Solution: Substring with Concatenation of All Words
Understand how to apply the sliding window technique to identify substrings that are concatenations of all given words in any order. Explore implementing an efficient solution in Go that uses fixed-size word blocks, frequency maps, and dynamic window adjustment to solve the problem with near-linear time complexity.
We'll cover the following...
Statement
You are given a string, s, and an array of strings, words. All strings in words are of the same length.
A concatenated string is a string that contains all the words in words exactly once, in any order, concatenated together without any intervening characters.
Formally, a concatenated string is a permutation of all words joined together. For example, if words = ["ab", "cd", "ef"], then the following are all valid concatenated strings: "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", "efcdab". However, "acdbef" is not valid because it is not formed by concatenating all the words in any order.
Your task is to return all starting indices of substrings in s that are concatenated strings.
You may return the indices in any order. ...