# Substring With Concatenation of All Words Problem Solution

Substring With Concatenation of All Words Problem: You are given a string `s` and an array of strings `words`. All the strings of `words` are of the same length.

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 :

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.

## Problem Solution In Python

``````class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if(len(words)==0):
return []
N = len(words[0])
if(len(s) < N*len(words)):
return []
i=0;location=[]
def recursion(firstWord,words,s,location,N):
if not words:
return location
if(firstWord in set(words)):
words.remove(firstWord)
pos = recursion(s[location+N:location+2*N],words,s,location+N,N)
if(pos == -1):
return -1
else:
return location
else:
return -1
while(i<len(s)):
firstWord = s[i:i+N]

pos = recursion(firstWord,words[:],s,i,N)

if(pos!=-1):
location.append(pos)
i+=1
return location
``````

## Problem Solution In Java

``````public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
if(words.length == 0 || words[0].length() == 0 || s.length() == 0) return res;
int wordLen = words[0].length();
int wordNum = words.length;
int windowSize = wordLen * wordNum;
Map<String,Integer> map = new HashMap<>();

for(String eachWord : words) {
map.put(eachWord,map.getOrDefault(eachWord,0) + 1);
}

for(int i = 0;i + windowSize - 1 < s.length();i++) {
String lastWord = s.substring(i + windowSize - wordLen,i + windowSize);
if(map.containsKey(lastWord)) {
boolean bre = false;
Map<String,Integer> currMap = new HashMap<>(map);
for(int j = i;j < i + windowSize;j += wordLen) {
String currWord = s.substring(j,j + wordLen);
currMap.put(currWord,currMap.getOrDefault(currWord,0) - 1);
if(currMap.get(currWord) < 0) {
bre = true;
break;
}
}
}
}
return res;
}
``````

## Problem Solution In C++

``````class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int>ans;
if(!s.size() || !words.size())
return ans;
unordered_map<string,int>mp1;
unordered_map<string,int>mp2;
for(auto word:words)
{
mp1[word]++;
}
int len = words.size();
int tl = words[0].size()*len;
int sl = words[0].size();
int i = 0;
if(tl>s.size())
return ans;
while(i<=s.size()-tl)
{

string sub = s.substr(i,tl);
int k = 0;
int n = 0;
while(k<words.size())
{
string temp = sub.substr(n,sl);
mp2[temp]++;
n += sl;
k++;
}
if(mp2 == mp1)
ans.push_back(i);
mp2.clear();
i++;
}
return ans;
}
};
``````

## Problem Solution In C

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

} dic_entry;

{
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;

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)
{

{
{
}
}
return NULL;
}

void reset(dic_entry* dic)
{

{
}
}

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

{
free(temp);
}
}

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
{
}

}

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;

}``````