educative.io

My solution used the same pattern as String Anagrams (Problem Challenge 2)

Courses
,
#1 
const find_word_concatenation = function(str, words) {
  result_indices = [];
  // this is the same as find starting indices of all anagrams
  // this just needs to jump windowEnd, windowStart by 3 instead of 1

  // create a frequencyMap from words
  const frequencyMap = {};
  for (i=0 ; i<words.length ; i++) {
    const word = words[i]; // cat
    if (word in frequencyMap) {
      frequencyMap[word] += 1;
    } else {
      frequencyMap[word] = 1;
    }
  }

  const wordLength = words[0].length;
  let windowStart = 0;
  let matched = 0;
  // form a sliding window in a stepwise fashion
  for (windowEnd = 0 ; windowEnd < str.length ; windowEnd += wordLength) {
    // check if current word in the window is an anagram of the words
    const rightWord = str.substring(windowEnd, windowEnd + wordLength);
    if (rightWord in frequencyMap) {
      frequencyMap[rightWord] -= 1;
      if (frequencyMap[rightWord] >= 0) {
        matched += 1;
      }
      
      // if true, insert the starting index to the result
      if (matched === words.length) {
        result_indices.push(windowStart);
      }
    }

    // if window length === words length (char length), shrink the window
    if (windowEnd - windowStart + wordLength === words.length * wordLength) {
      // shrink the window from the left, and adjust values in frequencyMap and matched
      const leftWord = str.substring(windowStart, windowStart + wordLength);
      if (leftWord in frequencyMap) {
        if (frequencyMap[leftWord] >= 0) {
          matched -= 1;
        }
        frequencyMap[leftWord] += 1;
      }
      windowStart += wordLength;
    }
  }

  // return result
  return result_indices;
}
#2

@Minjun_Youn

Yes, your solution seems fine :slight_smile: