What is the time complexity of Substring with Concatenation of All Words?

The optimal solution has a time complexity of O(n*m).

What data structures are used to solve Substring with Concatenation of All Words?

This problem uses Hash Table, String, Sliding Window. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Substring with Concatenation of All Words?

Insight 1: The core idea is to treat the problem as a sliding window. Since all words have the same length, we can move the window by the length of a word at a time. Insight 2: We can use a hash table (or Counter in Python) to store the counts of each word in the 'words' array. This allows for efficient comparison when checking if a substring is a valid concatenation.

Which companies ask LeetCode 30. Substring with Concatenation of All Words in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Bloomberg, Media.net and 5 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Substring with Concatenation of All Words - LeetCode 30 Solution

Substring with Concatenation of All Words - Complete Solution Guide

Substring with Concatenation of All Words is LeetCode problem 30, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given a string s and an array of strings words . All the strings of words are of the same length . A concatenated string is a string that exactly 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 string because it is not the concatenation of any permutation of words . Return an array of the starti

Detailed Explanation

The problem asks us to find all starting indices of substrings in a given string 's' that are formed by concatenating all the words from a given array 'words'. All words in the 'words' array have the same length. The order of words in the concatenated substring must match a permutation of the 'words' array. For instance, if words = ["ab","cd","ef"], then "abcdef", "abefcd", etc. are valid concatenated substrings, but "acdbef" is not. We should return a list of the starting indices of all such occurrences in 's'.

Solution Approach

The provided code uses a sliding window approach combined with hash tables to efficiently solve this problem. It iterates through the string 's' with a window of the size equal to the total length of the concatenated words. The core idea is to check for each possible starting position whether the substring of length `concat_len` can be formed by concatenating the words in `words`. To do this efficiently, it uses a hash map to store the counts of words in the original `words` array, and another hash map to track the counts of words within the current window. The outer loop iterates `wordLen` times to cover all possible offsets where a concatenated word might start, ensuring every potential substring is checked. The inner loop implements the sliding window, checking if words appear as expected and adjusting the window boundaries when necessary.

Step-by-Step Algorithm

Step 1: Handle edge cases where 's' or 'words' are empty or invalid.
Step 2: Calculate the length of each word, the number of words, and the total length of the concatenated string.
Step 3: Create a hash table (word_counts) to store the counts of each word in the 'words' array.
Step 4: Iterate 'word_len' times with 'r' from 0 to 'word_len' - 1. This loop essentially starts the search for concatenated words at every possible offset to cover all possible starting positions.
Step 5: Initialize the left boundary 'left' to 'r' and create a hash table (words_seen) to track the words seen in the current window.
Step 6: Iterate through the string 's' from 'r' with step 'word_len'. Extract a word (substring of length 'word_len') at each step.
Step 7: If the extracted 'word' is present in 'word_counts', update the 'words_seen' counter. If the count of a particular word in 'words_seen' exceeds its count in 'word_counts', shrink the window from the left until the counts match. This ensures the window contains a valid concatenation.
Step 8: If the length of the current window is equal to the total length of concatenated words ('concat_len'), add the starting index 'left' to the result list. This means a valid substring concatenation has been found.
Step 9: If the extracted 'word' is not present in 'word_counts', clear the 'words_seen' counter and move the left boundary to the next possible position. This indicates the current window cannot be a valid concatenation.
Step 10: Return the list of starting indices.

Key Insights

Insight 1: The core idea is to treat the problem as a sliding window. Since all words have the same length, we can move the window by the length of a word at a time.
Insight 2: We can use a hash table (or Counter in Python) to store the counts of each word in the 'words' array. This allows for efficient comparison when checking if a substring is a valid concatenation.
Insight 3: A naive approach could lead to TLE, so we must optimize the sliding window by only checking substrings of the exact length of the concatenation of all words and efficiently updating counts in the window.

Complexity Analysis

Time Complexity: O(n*m)

Space Complexity: O(m)

Topics

This problem involves: Hash Table, String, Sliding Window.

Companies

Asked at: Adobe, Amazon, Apple, Bloomberg, Media.net, Meta, Microsoft, Roku, Samsung, Zeta.

Substring with Concatenation of All Words | LeetCode 30

Hard

Hash Table String Sliding Window

Time: O(n*m)Space: O(m)

Solution Code

Available in:

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

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

        int wordLen = words[0].length();
        int numWords = words.length;
        int concatLen = wordLen * numWords;
        int sLen = s.length();

        if (sLen < concatLen) {
            return new ArrayList<>();
        }

        Map<String, Integer> wordCounts = new HashMap<>();
        for (String word : words) {
            wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1);
        }

        List<Integer> result = new ArrayList<>();

        for (int r = 0; r < wordLen; r++) {
            int left = r;
            Map<String, Integer> wordsSeen = new HashMap<>();

            for (int j = r; j <= sLen - wordLen; j += wordLen) {
                String word = s.substring(j, j + wordLen);

                if (wordCounts.containsKey(word)) {
                    wordsSeen.put(word, wordsSeen.getOrDefault(word, 0) + 1);

                    while (wordsSeen.get(word) > wordCounts.get(word)) {
                        String leftWord = s.substring(left, left + wordLen);
                        wordsSeen.put(leftWord, wordsSeen.get(leftWord) - 1);
                        left += wordLen;
                    }

                    if ((j - left) / wordLen + 1 == numWords) {
                        result.add(left);
                    }
                } else {
                    wordsSeen.clear();
                    left = j + wordLen;
                }
            }
        }

        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 30: Substring with Concatenation of All Words - Detailed explanation and solution approaches.

Topics

Hash Table String Sliding Window

Companies

AdobeAmazonAppleBloombergMedia.netMetaMicrosoftRoku

Stats

Difficulty:Hard

Languages:4

Companies:10

Problem #:30

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Handle edge cases where 's' or 'words' are empty or invalid.
2
Step 2: Calculate the length of each word, the number of words, and the total length of the concatenated string.
3
Step 3: Create a hash table (word_counts) to store the counts of each word in the 'words' array.
4
Step 4: Iterate 'word_len' times with 'r' from 0 to 'word_len' - 1. This loop essentially starts the search for concatenated words at every possible offset to cover all possible starting positions.
5
Step 5: Initialize the left boundary 'left' to 'r' and create a hash table (words_seen) to track the words seen in the current window.
6
Step 6: Iterate through the string 's' from 'r' with step 'word_len'. Extract a word (substring of length 'word_len') at each step.
7
Step 7: If the extracted 'word' is present in 'word_counts', update the 'words_seen' counter. If the count of a particular word in 'words_seen' exceeds its count in 'word_counts', shrink the window from the left until the counts match. This ensures the window contains a valid concatenation.
8
Step 8: If the length of the current window is equal to the total length of concatenated words ('concat_len'), add the starting index 'left' to the result list. This means a valid substring concatenation has been found.
9
Step 9: If the extracted 'word' is not present in 'word_counts', clear the 'words_seen' counter and move the left boundary to the next possible position. This indicates the current window cannot be a valid concatenation.
10
Step 10: Return the list of starting indices.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n*m)

💾

Space Complexity

O(m)

📝

Why?

The outer loop runs 'wordLen' times, which is bounded by the length of words which is a constant. The inner loop iterates over string 's' with a step size of 'wordLen'. In the worst case, this inner loop could go through almost the entirety of string 's'. For each iteration, operations like hash map lookups and updates take O(1) time on average. The space complexity comes from storing word counts and words seen in hash maps, both of which are bounded by the number of words in the 'words' array.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Generate all possible permutations of the 'words' array, then search for each permutation as a substring in 's'.

Time: O(m! * n), where n is the length of 's' and m is the number of words in 'words'. Generating permutations is m! and searching each permutation could take O(n).Space: O(m), for storing the permutations.

Trade-offs: Brute force is highly inefficient due to the factorial time complexity, making it unsuitable for larger inputs. The sliding window approach is generally preferred.

Using regular expressions

Construct a regular expression that matches any permutation of the given words and then use the regular expression engine to find all matches within the string s.

Time: Difficult to analyze accurately, but generally worse than the sliding window approach due to the overhead of regular expression matching.Space: O(m) for constructing the regular expression string.

Trade-offs: Can be cleaner to write but often performs worse and can be more difficult to debug or understand.

✨

Key Insights

1Insight 1: The core idea is to treat the problem as a sliding window. Since all words have the same length, we can move the window by the length of a word at a time.
2Insight 2: We can use a hash table (or Counter in Python) to store the counts of each word in the 'words' array. This allows for efficient comparison when checking if a substring is a valid concatenation.
3Insight 3: A naive approach could lead to TLE, so we must optimize the sliding window by only checking substrings of the exact length of the concatenation of all words and efficiently updating counts in the window.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Sliding Window

A moving "window" over data to process subsets efficiently.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string 's' or empty 'words' array. The code handles this by returning an empty list.
Edge case 2: The length of 's' is less than the total length of the concatenated words. The code handles this by returning an empty list.
Edge case 3: Duplicate words in 'words' array. The use of `Counter` ensures the algorithm handles duplicate words correctly.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling duplicate words correctly. Using `Counter` in Python, or `HashMap` and properly accounting for counts in other languages, is crucial to address this.

✗Common mistake 2: Not considering all possible starting positions. The outer loop, which iterates from 'r' = 0 to 'word_len' - 1, is vital to ensure all possible alignments are checked. Without it, a concatenated substring might be missed if it doesn't start at an index that's a multiple of 'word_len'.

✗Common mistake 3: Forgetting to shrink the window when a word's count exceeds its expected count. Failing to do so leads to false positives.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Text analysis and pattern recognition. This algorithm can be used to find specific sequences of words in a large text corpus.

🏦Real-world scenario 2: Bioinformatics. Identifying specific sequences of DNA or protein building blocks within a larger genetic sequence.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

👨‍💻 From Experience

I encountered a variation of this problem in a system design interview. The key was recognizing the underlying pattern.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 1, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

❓

Frequently Asked Questions

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Substring with Concatenation of All Words"?

For this hard-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?