Last updated on January 29th, 2025 at 02:33 am
Here, we see a Substring with Concatenation of All Words LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Hash Table, Sliding Window, String
Level of Question
Hard

Substring with Concatenation of All Words LeetCode Solution
Table of Contents
1. Problem Statement
You are given a string s and an array of strings words. All the strings of words are of the same length. Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.
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.
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: 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.
2. Coding Pattern Used in Solution
The provided code uses the Sliding Window pattern. This pattern is commonly used to solve problems involving contiguous subarrays or substrings. The sliding window approach involves maintaining a window (a range of indices) that satisfies certain conditions, and then sliding the window to explore other possibilities while maintaining efficiency.
3. Code Implementation in Different Languages
3.1 Substring with Concatenation of All Words C++
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> result; if (words.empty())return result; unordered_map<string, int> counts, record; for (string word : words) { counts[word]++; } int len = words[0].size(), num = words.size(), sl = s.size(); for (int i = 0; i < len; ++i) { int left = i, sum = 0; record.clear(); for (int j = i; j <= sl - len; j+=len) { string word = s.substr(j, len); if (counts.count(word)) { record[word]++; sum++; while (record[word] > counts[word]) { //remove the most left word record[s.substr(left, len)]--; left += len; sum--; } if (sum == num) result.push_back(left); } else { record.clear(); sum = 0; left = j + len; } } } return result; } };
3.2 Substring with Concatenation of All Words Java
class Solution { public List<Integer> findSubstring(String s, String[] words) { int N = s.length(); List<Integer> indexes = new ArrayList<Integer>(s.length()); if (words.length == 0) { return indexes; } int M = words[0].length(); if (N < M * words.length) { return indexes; } int last = N - M + 1; //map each string in words array to some index and compute target counters Map<String, Integer> mapping = new HashMap<String, Integer>(words.length); int [][] table = new int[2][words.length]; int failures = 0, index = 0; for (int i = 0; i < words.length; ++i) { Integer mapped = mapping.get(words[i]); if (mapped == null) { ++failures; mapping.put(words[i], index); mapped = index++; } ++table[0][mapped]; } //find all occurrences at string S and map them to their current integer, -1 means no such string is in words array int [] smapping = new int[last]; for (int i = 0; i < last; ++i) { String section = s.substring(i, i + M); Integer mapped = mapping.get(section); if (mapped == null) { smapping[i] = -1; } else { smapping[i] = mapped; } } //fix the number of linear scans for (int i = 0; i < M; ++i) { //reset scan variables int currentFailures = failures; //number of current mismatches int left = i, right = i; Arrays.fill(table[1], 0); //here, simple solve the minimum-window-substring problem while (right < last) { while (currentFailures > 0 && right < last) { int target = smapping[right]; if (target != -1 && ++table[1][target] == table[0][target]) { --currentFailures; } right += M; } while (currentFailures == 0 && left < right) { int target = smapping[left]; if (target != -1 && --table[1][target] == table[0][target] - 1) { int length = right - left; //instead of checking every window, we know exactly the length we want if ((length / M) == words.length) { indexes.add(left); } ++currentFailures; } left += M; } } } return indexes; } }
3.3 Substring with Concatenation of All Words JavaScript
var findSubstring = function(s, words) { let result = [], pattern = {}, wordLength = words[0].length; for (const word of words) { pattern[word] = (pattern[word] || 0) + 1; } for (let i = 0; i < wordLength; i++) { let back = i, front = back + wordLength, matches = {}, count = 0 while (front <= s.length) { let word = s.slice(front - wordLength, front); if (pattern[word]) { matches[word] = (matches[word] ?? 0) + 1; count++; while (matches[word] > pattern[word]) { matches[s.slice(back, back + wordLength)] -= 1; back += wordLength; count--; } if (count === words.length) { result.push(back) } } else { matches = {} count = 0; back = front; } front += wordLength; } } return result; };
3.4 Substring with Concatenation of All Words Python
class Solution(object): def findSubstring(self, s, words): wlen = len(words[0]) wslen = len(words) * len(words[0]) res = [] for pos in range(wlen): i = pos d = Counter(words) for j in range(i, len(s) + 1 - wlen, wlen): word = s[j: j + wlen] d[word] -= 1 while d[word] < 0: d[s[i: i + wlen]] += 1 i += wlen if i + wslen == j + wlen: res. append(i) return res
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n * m) | O(w) |
Java | O(n * m) | O(w) |
JavaScript | O(n * m) | O(w) |
Python | O(n * m) | O(w) |
where,
- N: Length of the string
s
. - M: Number of words in the
words
array. - W: Number of unique words in the
words
array. - len: Length of each word in the
words
array.