# Leetcode 30 Solution

https://leetcode.com/problems/substring-with-concatenation-of-all-words

## Thinking Process

First of all, an important and straightforward property is that a concatenated string’s size is `N * K`, if `N` is the size of `words`, and `K` is the length of each word.

Based on that, we can just find all the substrings in `s` with a length of `N * K`, and check to see if it is a concatenated string.

So the question now becomes how to check if a string is a concatenated string. This is basically to count the words from the concatenated string, and make sure these words match the given `words`. How do we do that? We keep a word count map for each of them. And if anytime, the word count map of the concatenated string has a count greater than the `words` word count map, it means this is not a concatenated string. Otherwise, it is one.

Applying the above algorithm for all the length `N * K` substrings in `s` solves the challenge.

## Time & Space Complexity

Assuming `M` is the size of `s`, `N` is the size of `words`, and `K` is the length of each word:

• Time complexity: `O((M - N * K) * N * K)`
• Space complexity: `O(M + N)`

## Solution

``````class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;

if (s.size() == 0 || words.size() == 0)
return res;

int n = words.size();
int m = words[0].size();

unordered_map<string, int> m1;
for (auto& word : words)
m1[word]++;

for (int i = 0; i <= (int)s.size() - m * n; i++)
{
unordered_map<string, int> m2;

int j;
for (j = 0; j < n; j++)
{
auto word = s.substr(i + j * m, m);
if (m1.find(word) == m1.end() || m2[word] >= m1[word])
break;
m2[word]++;
}

if (j == n)
res.push_back(i);
}

return res;
}
};
``````