# Substring with Concatenation of All Words LeetCode Solution

Here, We see Substring with Concatenation of All Words problem Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

## 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: 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.```
```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.
```

## Substring with Concatenation of All Words Leetcode Solution C++ ->

```.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```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.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;
}
};
```Code language: C++ (cpp)```

## Substring with Concatenation of All Words Leetcode Solution 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.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[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[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, 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[target] == table[target]) {
--currentFailures;
}
right += M;
}
while (currentFailures == 0 && left < right) {
int target = smapping[left];
if (target != -1 && --table[target] == table[target] - 1) {
int length = right - left;
//instead of checking every window, we know exactly the length we want
if ((length / M) ==  words.length) {
}
++currentFailures;
}
left += M;
}
}

}
return indexes;
}
}
```Code language: Java (java)```

## Substring with Concatenation of All Words Leetcode Solution JavaScript ->

``````var findSubstring = function(s, words) {
let result = [],
pattern = {},
wordLength = words.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;
};
```Code language: JavaScript (javascript)```

## Substring with Concatenation of All Words Leetcode Solution Python ->

``````class Solution(object):
def findSubstring(self, s, words):
wlen = len(words)
wslen = len(words) * len(words)
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
```Code language: Python (python)```

#### Jump Game II LeetCode Solution

You are given a 0-indexed array of integers nums of length n. You are initially…

#### First Missing Positive LeetCode Solution

Given an unsorted integer array nums, return the smallest missing positive integer.

#### Climbing Stairs LeetCode Solution

You are climbing a staircase. It takes n steps to reach the top. Each time you can…

#### Longest Palindromic Substring LeetCode Solution

Given a string s, return the longest palindromic substring in s. A palindrome is a string which reads the…