Substring with Concatenation of All Words

**Problem Statement:** Given the required input arguments, write an efficient algorithm to solve the **Substring with Concatenation of All Words** problem. Implement the required logic as specified by standard definitions for this classic algorithmic challenge. **Hint / Expected Approach:** Sliding window with word-frequency map **Edge Cases to Consider:** - (1) Word list has duplicates - (2) No valid substring - (3) s shorter than total words length

Examples

Example 1

Input: "barfoothefoobarman", ["foo","bar"]

Output: [0,9]

Example 2

Input: "wordgoodgoodgoodbestword", ["word","good","best","word"]

Output: []

Example 3

Input: "barfoofoobarthefoobarman", ["bar","foo","the"]

Output: [6,9,12]

Constraints

▪1 <= data.length <= 10^5
▪Memory complexity must be O(1) or O(k)
▪Ensure non-overlapping pointer access

Watch Out For Edge Cases

▪Word list has duplicates
▪No valid substring
▪s shorter than total words length

Frequently Asked At

GoogleAmazon

Back to Arena

hard

Sliding Window