Leetcode Substring with Concatenation of All Words problem solution YASH PAL, 31 July 2024 In this Leetcode Substring with Concatenation of All Words problem solution, we have given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters. You can return the answer in any order. Topics we are covering Toggle Problem solution in Python.Problem solution in Java.Problem solution in C++.Problem solution in C. 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; } } if(!bre)res.add(i); } } 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* 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) { head = new_entry; } else { while(dic->next) { dic = dic->next; } dic->next = new_entry; } return head; } dic_entry* find_entry(dic_entry* dic, char* word, int len) { dic_entry* head = dic; while(head) { if(!strncmp(head->word, word, len)) { return head; } head = head->next; } return NULL; } void reset(dic_entry* dic) { dic_entry* head = dic; while(head) { head->occurred = 0; head = head->next; } } void free_dic(dic_entry* dic) { dic_entry* head = dic; dic_entry* temp; while(head) { free(head->word); temp = head; head = head->next; 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 { 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; } coding problems solutions