Substring with Concatenation of All Words

LeetCode 30 | Difficulty: Hard

Hard

Problem Description

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

- For example, if `words = ["ab","cd","ef"]`, then `"abcdef"`, `"abefcd"`, `"cdabef"`, `"cdefab"`, `"efabcd"`, and `"efcdab"` are all concatenated strings. `"acdbef"` is not a concatenated string because it is not the concatenation of any permutation of `words`.

Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]

Output: [0,9]

Explanation:

The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.

The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]

Output: []

Explanation:

There is no concatenated substring.

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]

Output: [6,9,12]

Explanation:

The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"].

The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"].

The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"].

Constraints:

- `1 <= s.length <= 10^4`

- `1 <= words.length <= 5000`

- `1 <= words[i].length <= 30`

- `s` and `words[i]` consist of lowercase English letters.

Topics: Hash Table, String, Sliding Window

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 1091 ms)

Metric	Value
Runtime	1091 ms
Memory	45 MB
Date	2022-01-26

Solution

public class Solution {
    public IList<int> FindSubstring(string s, string[] words) {
       int n = words.Length;
    bool[] used = new bool[n];
    int wordLen = words[0].Length;
    IList<int> indexes = new List<int>();
    for (int i = 0; i <= s.Length-(n*wordLen); i++)
    {
        if(FindDfs(s, i, wordLen, words, used, n))
        indexes.Add(i);
    }
    return indexes;
}

private bool FindDfs(string s, int index, int wordLen, string[] words, bool[] used, int count)
{
    if(count==0) return true;
    string substr = s.Substring(index, wordLen);
    for(int i=0;i<words.Length;i++)
    {
        if(words[i].Equals(substr) && !used[i])
        {
            used[i] = true;
            bool result = FindDfs(s, index + wordLen, wordLen, words, used, count - 1);
            used[i] = false;
            return result;
        }
    }
    return false;       
}
}

📜 2 more C# submission(s)

Submission (2022-01-19) — 1335 ms, 44.7 MB

public class Solution {
    public IList<int> FindSubstring(string s, string[] words) {
       int n = words.Length;
    bool[] used = new bool[n];
    int wordLen = words[0].Length;
    IList<int> indexes = new List<int>();
    for (int i = 0; i <= s.Length-(n*wordLen); i++)
    {
        if(FindDfs(s, i, wordLen, words, used, n))
        indexes.Add(i);
    }
    return indexes;
}

private bool FindDfs(string s, int index, int wordLen, string[] words, bool[] used, int count)
{
    if(count==0) return true;
    string substr = s.Substring(index, wordLen);
    for(int i=0;i<words.Length;i++)
    {
        if(words[i].Equals(substr) && !used[i])
        {
            used[i] = true;
            bool result = FindDfs(s, index + wordLen, wordLen, words, used, count - 1);
            used[i] = false;
            return result;
        }
    }
    return false;       
}
}

Submission (2022-01-26) — 1421 ms, 44.9 MB

public class Solution {
    public IList<int> FindSubstring(string s, string[] words)
{
    int n = words.Length;
    bool[] used = new bool[n];
    int wordLen = words[0].Length;
    IList<int> indexes = new List<int>();
    for (int i = 0; i <= s.Length-(n*wordLen); i++)
    {
        if(FindDfs(s, i, wordLen, words, used, n))
        indexes.Add(i);
    }
    return indexes;
}

private bool FindDfs(string s, int index, int wordLen, string[] words, bool[] used, int count)
{
    if(count==0) return true;
    string substr = s.Substring(index, wordLen);
    for(int i=0;i<words.Length;i++)
    {
        //handling duplicate words condition by goinf over all words which are equal and not used
        if(words[i].Equals(substr) && !used[i])
        {
            used[i] = true;
            bool result = FindDfs(s, index + wordLen, wordLen, words, used, count - 1);
            used[i] = false;
            return result;
        }
    }
    return false;       
}
}

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Hash map gives O(1) lookup — think about what to use as key vs value.