Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 4: Words Concatenation (hard)

Problem Statement

You’re given a string s and a list of words words, where all words have the same length.

A concatenated substring is formed by joining all the words from any permutation of words — each used exactly once, without any extra characters in between.

For example, if words = ["ab", "cd", "ef"], then valid concatenated strings include "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab". A string like "acdbef" is not valid because it doesn't match any complete permutation of the given words.

Return all starting indices in `s

.....

.....

.....

Like the course? Get enrolled and start learning!
F

Fah Pariyavuth

· 4 years ago

The solution is not Sliding Window. For example, this is equivalent to Solution 1 in the equivalent Leetcode problem. Rather we should look to implement Solution 2 which is a true Sliding Window solution and has much better runtime. O(M + N*Len) as opposed to O(N * M * Len) https://leetcode.com/problems/substring-with-concatenation-of-all-words/solution/

A

Ada

· 5 years ago

This needs a code comment on the first loop's signature.

Show 4 replies
A

Alexander Bondarenko

· 5 years ago

I'm wondering why the time complexity is O(N * M * Len) and not O(N * M)?

Show 1 reply
K

K D

· 4 years ago

What is the pattern for longest palindromic substring?

L

linochoa11690

· 4 years ago

does anyone know what the OR 0 means in the JS code?

if (wordsSeen[word] > (wordFrequency[word] || 0)) {

thanks in advance!

Show 1 reply
S

sean.maginnis.sm

· 2 years ago

Your Input"catfoxscat" ["cat", "foxs"] Output[] Expected[]

This was marked as correct however......

you can get "catfoxs" & "foxscat"

so the the correct result is [0,3]

the solution uses words[0].length();

This means that if you ever have words of different lengths then the test fails.

Show 1 reply
S

Sukumar

· 4 years ago

public static List wordConcatenation(String inputString, String [] wordsList) { List resultIndices = new ArrayList(); Map givenWordsMap = new HashMap(); int noOfWords = wordsList.length; int wordLength = wordsList[0].length(); int resultStringLength = wordLength * noOfWords; for(String s : wordsList) givenWordsMap.put(s, givenWordsMap.getOrDefault(s, 0) + 1); for(int i = 0; i < wordLength; i++) { Map foundWordsMap = new HashMap(); int leftWindow = i; int matchCount = 0; for(int rightWindow = leftWindow; rightWindow

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
    def findWordConcatenation(self, text, words):
        result_indices = []  # List to store the starting indices of valid substrings
        word_len = len(words[0])  # Length of each word
        total_words = len(words)  # Total number of words
        word_freq = {}  # Hashmap to store word frequencies

        # Initialize word frequency hashmap
        for word in words:
            word_freq[word] = word_freq.get(word, 0) + 1

        # Slide the window through the text
        for i in range(len(text) - total_words * word_len + 1):
            curr_window = text[i:i + total_words * word_len]  # Current substring
            curr_word_count = {}  # Hashmap to store word frequencies in the current window

            # Count word frequencies in the cur
Show 1 reply
Adam

Adam

· 2 years ago

Actually solution provided in the course with O(NML) is not amazing. This problem can be solved effectively in O(NL).

her ta

her ta

· 2 years ago

"itwasbestoftimes" ["it","was","best"]

Output[0] Expected[]