LeetCode Problem – 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 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.

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

Constraints:

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

Java Solution

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ConcatenationSubstring {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return result;
        }

        int wordLength = words[0].length();
        int totalWords = words.length;
        int totalLength = wordLength * totalWords;
        Map<String, Integer> wordCountMap = new HashMap<>();

        // Count occurrences of each word in the words array
        for (String word : words) {
            wordCountMap.put(word, wordCountMap.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i <= s.length() - totalLength; i++) {
            String substring = s.substring(i, i + totalLength);
            Map<String, Integer> tempMap = new HashMap<>(wordCountMap);

            // Check if the current substring is a valid concatenation
            for (int j = 0; j < totalLength; j += wordLength) {
                String word = substring.substring(j, j + wordLength);
                if (!tempMap.containsKey(word) || tempMap.get(word) == 0) {
                    break;
                }
                tempMap.put(word, tempMap.get(word) - 1);
                if (j == totalLength - wordLength) {
                    result.add(i);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        ConcatenationSubstring solution = new ConcatenationSubstring();

        // Example 1
        String s1 = "barfoothefoobarman";
        String[] words1 = {"foo", "bar"};
        System.out.println("Example 1 Output: " + solution.findSubstring(s1, words1));

        // Example 2
        String s2 = "wordgoodgoodgoodbestword";
        String[] words2 = {"word", "good", "best", "word"};
        System.out.println("Example 2 Output: " + solution.findSubstring(s2, words2));

        // Example 3
        String s3 = "barfoofoobarthefoobarman";
        String[] words3 = {"bar", "foo", "the"};
        System.out.println("Example 3 Output: " + solution.findSubstring(s3, words3));
    }
}

This program defines a ConcatenationSubstring class with a findSubstring method to find the starting indices of all concatenated substrings. The main method demonstrates how to use the program with the provided examples.

Python Solution

from collections import Counter

class ConcatenationSubstring:
    def findSubstring(self, s, words):
        result = []
        if not s or not words:
            return result

        word_length = len(words[0])
        total_words = len(words)
        total_length = word_length * total_words
        word_count_map = Counter(words)

        for i in range(len(s) - total_length + 1):
            substring = s[i:i + total_length]
            temp_map = word_count_map.copy()

            # Check if the current substring is a valid concatenation
            for j in range(0, total_length, word_length):
                word = substring[j:j + word_length]
                if word not in temp_map or temp_map[word] == 0:
                    break
                temp_map[word] -= 1
                if j == total_length - word_length:
                    result.append(i)

        return result

# Example usage:
solution = ConcatenationSubstring()

# Example 1
s1 = "barfoothefoobarman"
words1 = ["foo", "bar"]
print("Example 1 Output:", solution.findSubstring(s1, words1))

# Example 2
s2 = "wordgoodgoodgoodbestword"
words2 = ["word", "good", "best", "word"]
print("Example 2 Output:", solution.findSubstring(s2, words2))

# Example 3
s3 = "barfoofoobarthefoobarman"
words3 = ["bar", "foo", "the"]
print("Example 3 Output:", solution.findSubstring(s3, words3))

This Python code mirrors the Java solution. It defines a ConcatenationSubstring class with a findSubstring method to find the starting indices of all concatenated substrings. The example usage section demonstrates how to use the program with the provided examples.