# Leetcode Substring with Concatenation of All Words problem solution

Feb 26, 2023

In the Leetcode Substring with Concatenation of All Words problem solution You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated substring in s is a substring that 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 substring because it is not the concatenation of any permutation of words.
Return 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: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6.
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.
The output order does not matter. Returning [9,0] is fine too.

Example 2:

Input: s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]
Output: []
Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16.
There is no substring of length 16 is s that is equal to the concatenation of any permutation of words.
We return an empty array.

Example 3:

Input: s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]
Output: [6,9,12]
Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9.
The substring starting at 6 is “foobarthe”. It is the concatenation of [“foo”,”bar”,”the”] which is a permutation of words.
The substring starting at 9 is “barthefoo”. It is the concatenation of [“bar”,”the”,”foo”] which is a permutation of words.
The substring starting at 12 is “thefoobar”. It is the concatenation of [“the”,”foo”,”bar”] which is a permutation of words.

Constraints:

• 1 <= s.length <= 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• s and words[i] consist of lowercase English letters.

## Solution in C Programming

``````typedef struct entry{
char* word;
int occurred;
int occurrence;
struct entry* next;

} dic_entry;

dic_entry* add_entry(dic_entry* dic, char* word)
{
dic_entry* new_entry = (dic_entry*)malloc(sizeof(dic_entry));
new_entry->word = (char*)malloc(sizeof(char)*(strlen(word)+1));
strcpy(new_entry->word, word);
new_entry->occurred = 0;
new_entry->occurrence = 1;
new_entry->next = NULL;
dic_entry* head = dic;

if(dic == NULL)
{
}
else
{
while(dic->next)
{
dic = dic->next;
}

dic->next = new_entry;
}
}

dic_entry* find_entry(dic_entry* dic, char* word, int len)
{

dic_entry* head = dic;
{
{
}
}
return NULL;
}

void reset(dic_entry* dic)
{
dic_entry* head = dic;

{
}
}

void free_dic(dic_entry* dic)
{
dic_entry* head = dic;
dic_entry* temp;

{
free(temp);
}
}

/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){

int* result = (int*)malloc(sizeof(int));
int resultCount = 0;
dic_entry* dic = NULL;
dic_entry* temp;
int j;
int string_len = (int)strlen(s);

if (wordsSize == 0)
{
*returnSize = 0;
return result;
}

int word_len = strlen(words[0]);

for(int i = 0; i < wordsSize; i++)
{

temp = find_entry(dic, words[i], word_len);

if(temp != NULL)
{
temp->occurrence++;
}
else
{
dic = add_entry(dic, words[i]);
}

}

for(int i = 0; i <= string_len - wordsSize*word_len; i++)
{
for(j = 0; j < wordsSize; j++)
{
temp = find_entry(dic, s+j*word_len+i, word_len);
if(temp)
{
temp->occurred++;
if (temp->occurred > temp->occurrence)
break;
}
else
{
break;
}
}

if(j == wordsSize)
{
result[resultCount++] = i;
result = (int*)realloc(result, sizeof(int)*(resultCount+1));
}

reset(dic);
}

free_dic(dic);
*returnSize = resultCount;
return result;

}``````

## Solution in C++ Programming

``````class Solution {
public:

bool isWindowContainsSubstring(string &s, int start, int end, int &wordSize, map<string, int> &hash){

map<string, int> temp;
string subStr;

while(start < end){

subStr = s.substr(start, wordSize);
temp[subStr]+=1;

if( hash[subStr] < temp[subStr] ) return false;

start += wordSize;
}
return true;
}

vector<int> findSubstring(string s, vector<string>& words) {

int wordSize = words[0].length(), windowSize = words.size() * wordSize, n = s.length();
int charsHash[26] = {0}, temp[26] = {0}, charsFound = 0, start=0;
map<string, int> wordsHash;
vector<int> ans;

for(auto &str : words){
wordsHash[str]++;
for(auto &ch : str) charsHash[ch-97]++;
}

for(int i=0;i<n;i++){

temp[s[i]-97]++;
charsFound = (charsHash[s[i]-97] > 0)? charsFound + 1 : charsFound;

while( start <= i && temp[s[i]-97] > charsHash[s[i]-97] ){
charsFound = (charsHash[s[start]-97] > 0)? charsFound - 1 : charsFound;
temp[s[start]-97] -= 1;
start++;
}

if( charsFound == windowSize ){

if( isWindowContainsSubstring(s, start, i+1, wordSize, wordsHash) ) ans.push_back(start);
}
}
return ans;
}
};``````

## Solution in Java Programming

``````class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
if(s == null || s.length() == 0 || words == null || words.length == 0) return res;
HashMap<String, Integer> map = new HashMap<>();
for(String word: words){
map.put(word, map.getOrDefault(word, 0) + 1);
}
int wordLength = words[0].length(), totalLength = words.length;
for(int i = 0; i < s.length() - wordLength * totalLength + 1; i++){
HashMap<String, Integer> tmp = new HashMap<>();
int j = 0;
while(j < totalLength){
String cur = s.substring(i + j * wordLength, i + (j + 1) * wordLength);
if(map.containsKey(cur)){
tmp.put(cur, tmp.getOrDefault(cur, 0) + 1);
if(tmp.get(cur) > map.get(cur)){
break;
}
}else{
break;
}
j++;
}
if(j == totalLength){
}

}
return res;
}
}``````

## Solution in Python Programming

``````class Solution(object):
def findSubstring(self, s, words):
if not s or not words:
return []
from collections import Counter
d_original = Counter(words)
l = []
s_len = len(s)
length = len(words)
len_words = len(words[0])
total_length = length * len_words
c = 0
while c <= s_len - total_length:
sliced = s[c:c + total_length]
d = d_original.copy()
for i in range(0, total_length, len_words):
A = sliced[i: i + len_words]
if d.get(A, -1) > 0:
d[A] = d[A] - 1
if sum(d.values()) == 0:
l.append(c)
c = c + 1
return l``````

## Solution in C# Programming

``````public class Solution {
public IList<int> FindSubstring(string s, string[] words) {
List<int> result = new();
int wordLength = words[0].Length;
Dictionary<string, int> wordCount = words.GroupBy(w => w).ToDictionary(g => g.Key, g => g.Count());

for (int offset = 0; offset < wordLength; offset++)
{
Queue<string> queue = new (words.Length + 1);
int invalidCounter = 0;
for (int i = 0; i < (s.Length - offset) / wordLength; i++)
{
string word = s.Substring(offset + i * wordLength, wordLength);

if (wordCount.ContainsKey(word))
{
if (--wordCount[word] == -1)
invalidCounter++;
queue.Enqueue(word);
}
else
{
while (queue.Count > 0)
wordCount[queue.Dequeue()]++;
invalidCounter = 0;
}

if (queue.Count > words.Length)
if (++wordCount[queue.Dequeue()] == 0)
invalidCounter--;

if (invalidCounter == 0 && queue.Count == words.Length)
result.Add(offset + (i - words.Length + 1) * wordLength);
}

while (queue.Count > 0)
wordCount[queue.Dequeue()]++;
}

return result;
}
}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.