Solution: Substring with Concatenation of All Words
Explore how to solve the substring concatenation problem by applying the sliding window technique. Understand how to use word frequencies and dynamic window boundaries to identify valid concatenations in a string efficiently. This lesson guides you through implementing an approach that optimizes search for these substrings in near-linear time.
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. ...