30. Substring with Concatenation of All Words
Approach
Slide a window of total-word-length across the string; use a
frequency map to verify the window contains exactly the required words.
Key Techniques
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
The sliding window technique maintains a dynamic sub-array (or substring) of interest, expanding the right boundary and shrinking the left boundary based on a constraint. It reduces O(n²) substring enumeration to O(n). Track state (frequency map, sum, distinct count) incrementally.
// Approach: Slide a window of total-word-length across the string; use a
// frequency map to verify the window contains exactly the required words.
// Time: O(n*w) Space: O(k)
public class Solution
{
public IList<int> FindSubstring(string s, string[] words)
{
IList<int> indices = new List<int>();
if (s == null || words == null || words.Length == 0)
return indices;
Dictionary<string, int> map = new Dictionary<string, int>();
for (int i = 0; i < words.Length; i++)
{
if (map.ContainsKey(words[i]))
{
map[words[i]] += 1;
}
else
map.Add(words[i], 1);
}
int wordLen = words[0].Length;
int windowLen = words.Length * wordLen;
for (int i = 0; i <= s.Length - windowLen; i++)
{
Dictionary<string, int> subMap = new Dictionary<string, int>(map);
int j = i;
while (j < i + windowLen)
{
string currWord = s.Substring(j, wordLen);
if (!subMap.ContainsKey(currWord))
{
//Console.WriteLine("Not int the map");
break;
}
else
{
if (subMap[currWord] > 1)
subMap[currWord] -= 1;
else
subMap.Remove(currWord);
}
//Console.WriteLine("Current word: "+ currWord + " j value: " + j + " Count: " + subMap.Count);
j = j + wordLen;
}
if (subMap.Count > 0)
continue;
if (j == i + windowLen)
indices.Add(i);
}
return indices;
}
}