30. Substring with Concatenation of All Words LeetCode Solution
In this guide we will provide 30. Substring with Concatenation of All Words LeetCode Solution with best time and space complexity. The solution to Substring with Concatenation of All Words problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.
Problem Statement of Substring with Concatenation of All Words
You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated string is a string that exactly 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 string because it is not the concatenation of any permutation of words.
Return an array of 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:
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.
Input: s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]
Output: []
Explanation:
There is no concatenated substring.
Example 3:
Input: s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]
Output: [6,9,12]
Explanation:
The substring starting at 6 is “foobarthe”. It is the concatenation of [“foo”,”bar”,”the”].
The substring starting at 9 is “barthefoo”. It is the concatenation of [“bar”,”the”,”foo”].
The substring starting at 12 is “thefoobar”. It is the concatenation of [“the”,”foo”,”bar”].
Constraints:
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
s and words[i] consist of lowercase English letters.
Complexity Analysis
Time Complexity: O(|\texttt{s}||\texttt{words}||\texttt{words[0]}|)
Space Complexity: O(\Sigma |\texttt{words[i]}|)
30. Substring with Concatenation of All Words LeetCode Solution in C++
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
if (s.empty() || words.empty())
return {};
const int k = words.size();
const int n = words[0].length();
vector<int> ans;
unordered_map<string, int> count;
for (const string& word : words)
++count[word];
for (int i = 0; i < s.length() - k * n + 1; ++i) {
unordered_map<string, int> seen;
int j;
for (j = 0; j < k; ++j) {
const string& word = s.substr(i + j * n, n);
if (++seen[word] > count[word])
break;
}
if (j == k)
ans.push_back(i);
}
return ans;
}
}; /* code provided by PROGIEZ */
30. Substring with Concatenation of All Words LeetCode Solution in Java
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
if (s.isEmpty() || words.length == 0)
return new ArrayList<>();
final int k = words.length;
final int n = words[0].length();
List<Integer> ans = new ArrayList<>();
Map<String, Integer> count = new HashMap<>();
for (final String word : words)
count.merge(word, 1, Integer::sum);
for (int i = 0; i <= s.length() - k * n; ++i) {
Map<String, Integer> seen = new HashMap<>();
int j = 0;
for (; j < k; ++j) {
final String word = s.substring(i + j * n, i + j * n + n);
seen.merge(word, 1, Integer::sum);
if (seen.get(word) > count.getOrDefault(word, 0))
break;
}
if (j == k)
ans.add(i);
}
return ans;
}
} // code provided by PROGIEZ
30. Substring with Concatenation of All Words LeetCode Solution in Python
class Solution:
def findSubstring(self, s: str, words: list[str]) -> list[int]:
if len(s) == 0 or words == []:
return []
k = len(words)
n = len(words[0])
ans = []
count = collections.Counter(words)
for i in range(len(s) - k * n + 1):
seen = collections.defaultdict(int)
j = 0
while j < k:
word = s[i + j * n: i + j * n + n]
seen[word] += 1
if seen[word] > count[word]:
break
j += 1
if j == k:
ans.append(i)
return ans #code by PROGIEZ
