Substring with Concatenation of All Words Leetcode Solution

In this post, you will know how to solve the Substring with Concatenation of All Words Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Substring with Concatenation of All Words Leetcode Solution
Substring with Concatenation of All Words Leetcode Solutions

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

You are given a string s and an array of strings words. All the strings of words are of the same length.

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.

Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Ex 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.

Ex3:

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.

Constraints:

  • 1 <= s.length <= 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • s and words[i] consist of lowercase English letters.

Substring with Concatenation of All Words Leetcode Solutions 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 = Counter(words)
    for i in range(len(s) - k * n + 1):
      seen = 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

Substring with Concatenation of All Words Leetcode Solutions in CPP

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;
  }
};

Substring with Concatenation of All Words Leetcode Solutions 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.put(word, count.getOrDefault(word, 0) + 1);
    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.put(word, seen.getOrDefault(word, 0) + 1);
        if (seen.get(word) > count.getOrDefault(word, 0))
          break;
      }
      if (j == k)
        ans.add(i);
    }
    return ans;
  }
}

Note: This problem Substring with Concatenation of All Words is generated by Leetcode but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Next: Next Permutation Leetcode Solution

Leave a Reply

Your email address will not be published. Required fields are marked *