DevExCode

LeetCode 30: Substring with Concatenation of All Words Solution

Master LeetCode problem 30 (Substring with Concatenation of All Words), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

30. Substring with Concatenation of All Words

Hard
Hash TableStringSliding Window

Problem Explanation

Explanation

To solve this problem, we can use a sliding window approach. We will iterate through all possible starting indices for the substring of length words.length * words[0].length() in the string s. At each iteration, we will check if the substring starting at the current index is a concatenation of all words. To achieve this, we can use a hashmap to store the frequency of each word in words and compare the current substring with this hashmap.

  1. We first calculate the length of each word in words (let's call it wordLen) and the total length of all words combined.
  2. We create a hashmap wordFreq to store the frequency of each word in words.
  3. We iterate through all possible starting indices for the substring in s.
  4. At each iteration, we create a hashmap currFreq to store the frequency of words in the current substring.
  5. We divide the current substring into words of length wordLen and check if each word is present in wordFreq.
  6. If a word is not present or its frequency in currFreq exceeds its frequency in wordFreq, we break out of the loop and move to the next starting index.
  7. If the current substring is a concatenation of all words, we add the starting index to the result.
  8. Finally, we return the list of starting indices where concatenated substrings are found.

Solution Code

import java.util.*;

class Solution {
    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 wordLen = words[0].length();
        int totalLen = wordLen * words.length;
        Map<String, Integer> wordFreq = new HashMap<>();
        for (String word : words) {
            wordFreq.put(word, wordFreq.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i <= s.length() - totalLen; i++) {
            Map<String, Integer> currFreq = new HashMap<>();
            int j = 0;
            while (j < words.length) {
                String currWord = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
                if (!wordFreq.containsKey(currWord)) {
                    break;
                }
                currFreq.put(currWord, currFreq.getOrDefault(currWord, 0) + 1);
                if (currFreq.get(currWord) > wordFreq.get(currWord)) {
                    break;
                }
                j++;
            }
            if (j == words.length) {
                result.add(i);
            }
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 30 (Substring with Concatenation of All Words)?

This page provides optimized solutions for LeetCode problem 30 (Substring with Concatenation of All Words) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 30 (Substring with Concatenation of All Words)?

The time complexity for LeetCode 30 (Substring with Concatenation of All Words) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 30 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 30 in Java, C++, or Python.

Back to LeetCode Solutions