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.