Practice/Google/Leetcode 30. Substring with Concatenation of All Words

Leetcode 30. Substring with Concatenation of All Words

CodingOptional

Problem

You are given a string s and an array words where each word in the array has the same length. Your task is to identify all starting positions in s where a substring can be formed by concatenating each word from words exactly once, in any order.

Return a list of all such starting indices. The indices can be returned in any order.

Requirements

1. Each word in words must appear exactly once in the valid substring
2. All words in words have identical length
3. The concatenation can occur in any order
4. Find all possible starting indices where such concatenations exist
5. Return the result as a list of integers representing starting positions

Constraints

• 1 ≤ s.length ≤ 10⁴
• 1 ≤ words.length ≤ 5000
• 1 ≤ words[i].length ≤ 30
• s and words[i] consist of lowercase English letters
• All strings in words have the same length

Examples

Example 1:

` Input: s = "barfoothefoobarman", words = ["foo", "bar"] Output: [0, 9] Explanation:

• Starting at index 0: "barfoo" is a concatenation of "bar" + "foo"
• Starting at index 9: "foobar" is a concatenation of "foo" + "bar" `

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word", "good", "best", "word"] Output: [] Explanation: No position in s contains a valid concatenation of all four words exactly once each.

Example 3:

` Input: s = "barfoofoobarthefoobarman", words = ["bar", "foo", "foo"] Output: [0, 6] Explanation:

• Starting at index 0: "barfoofoo" contains "bar" once and "foo" twice
• Starting at index 6: "foobarfoo" contains "foo" twice and "bar" once (rearranged) `