Table of Contents
Problem Statement
The Substring with Concatenation of All Words LeetCode Solution – “Substring with Concatenation of All Words” states that given a string s and an array of string words where each word is of the same length. We need to return all starting indices of the substring that is the concatenation of each word in words exactly once, in any order without any intervening characters.
Example:
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation:
- Substring starting at index 0 is: “barfoo”.
- Substring starting at index 9 is: “foobar”.
- Hence, answer is [0, 9].
Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation:
- There doesn’t exist any required substring.
Approach
Idea:
- The main idea to solve this problem is to use HashSet or Sliding Window.
- Since the length of each word is fixed, we will iterate for fixed-length L in the input string and use the sliding window technique to find whenever there is an exact match of frequencies of all distinct characters, then we store the starting index of the current window.
- First, store frequencies of strings in a HashSet.
- Now, iterate for fixed-length L for every i in the range [0, L – 1].
- Whenever we find a substring of length L which doesn’t occur in HashSet, then we cannot have the required substring containing all words present in an array of strings of words hence, we reset all the values.
- Otherwise, increment the frequency of the current substring in our HashSet and when this value matches with the desired frequency, we will increment our match count.
- Whenever the frequency of the current substring exceeds the desired frequency, we will shorten the start index of the window and modify the match count respectively.
- Whenever the match count equals to the desired match count, we will store the starting index of the current window.
Code
Substring with Concatenation of All Words Leetcode C++ Solution:
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map <string, int> occ;
for(auto& word : words){
occ[word]++;
}
vector <int> ans;
int sz = occ.size();
int n = s.length(), m = words.size(), len = words.back().length();
for(int i=0; i<len; i++){
int start = i, match = 0;
unordered_map <string, int> now;
for(int end=i+len-1; end<n; end+=len){
string str = s.substr(end-len+1, len);
if(!occ.count(str)){
now.clear();
match = 0;
start = end + 1;
}
else{
now[str]++;
if(now[str] == occ[str]){
match++;
}
while(now[str] > occ[str]){
if(now[s.substr(start, len)] == occ[s.substr(start, len)]){
match--;
}
now[s.substr(start, len)]--;
if(now[s.substr(start, len)] == 0){
now.erase(s.substr(start, len));
}
start += len;
}
if(match == sz){
ans.push_back(start);
}
}
}
}
return ans;
}
};Substring with Concatenation of All Words Leetcode Java Solution:
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<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];
}
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;
}
}
for (int i = 0; i < M; ++i) {
int currentFailures = failures;
int left = i, right = i;
Arrays.fill(table[1], 0);
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;
if ((length / M) == words.length) {
indexes.add(left);
}
++currentFailures;
}
left += M;
}
}
}
return indexes;
}
}Complexity Analysis for Substring with Concatenation of All Words Leetcode Solution
Time Complexity
The time complexity of the above code is O(N*L + M) since we traverse the entire input array twice (sliding window technique) and for each position, we’re extracting the substring of length L, here N = size of the string s, L = length of each word, M = size of the array of words.
Space Complexity
The space complexity of the above code is O(M).