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!
Vishwajeet Thoke

Vishwajeet Thoke

· 4 months ago

//Optimal solution in CPP:

using namespace std;

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

class Solution {
   public:
    vector<int> findWordConcatenation(const string& str, const vector<string>& words) {
        vector<int> resultIndices;
        // TODO: Write your code here
        int wordSize = words[0].length();
        for (int k = 0; k < wordSize; k++) {
            int windowStart = k;
            int matched = 0;
            unordered_map<string, int> freqMap;
            for (auto it : words)
                freqMap[it]++;
            for (int windowEnd = wordSize - 1 + k; windowEnd < str.length(); windowEnd = windowEnd + wordSize) {
                if (windowStart > ((int)str.length() - (wordSize * (int)words.size())))
Show 1 reply
Kushak Zohaad Jafry

Kushak Zohaad Jafry

· 8 months ago

class Solution {
  findWordConcatenation(str, words) {
    const resultIndices = [];
    const wordLen = words[0].length;
    const numWords = words.length;
    const totalLen = wordLen * numWords;
    // TODO: Write your code here
    let wordsFreqMap = new Map();
    for(let i=0; i<words.length; i++) {
      wordsFreqMap.set(words[i], (wordsFreqMap.get(words[i]) || 0) + 1);
    }
    const uniqueWordsToMatch = wordsFreqMap.size;
    for (let offset = 0; offset < wordLen; offset++) {
      let windowStart = offset;
      let windowEnd = offset;
      let wordsMatched = 0;
    const currWordsCount = new Map();

      while(windowEnd + wordLen <= str.length) {
        const currWord = str.substring(windowEnd, windowEnd + wordLen);
        windowEnd += wordLen;
        if(words
Show 1 reply
her ta

her ta

· 2 years ago

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

Output[0] Expected[]

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 2 replies
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).

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
K

K D

· 4 years ago

What is the pattern for longest palindromic substring?

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
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
A

Ada

· 5 years ago

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

Show 4 replies

Reading Progress

0%

Vote for new content