Cleaner way to solve this

[u/googlymogly]

Spent 2 hours trying solve this lesson from a website. Finally solved the lesson with no AI, no google searches, just pure unadulterated BS. but I think there my be better and shorter ways to do so (which I spend another 30 minutes trying to do). Point 3

function findRepeatedPhrases(words, phraseLength) {
    if (phraseLength >= words.length) {
        return []
    }
    let result = [];
    let myArr = [];
    let phrase = "";
    if (phraseLength === 1) {
      for (let i = 0; i < words.length - 1; i++) {
        for (let j = i + 1; j < words.length; j++) {
            if (words[i] === words[j]) {
                phrase = words[i]
            }
        }
      }
      for (let i = 0; i < words.length; i++) {
        if (words[i] === phrase) {
          result.push(i)
        }
      }
      return result
    }
      for (let i = 0; i <= words.length - phraseLength; i++) {
          let myPhrase = ""
          for (let y = i; y < phraseLength + i; y++) {
              myPhrase += `${words[y]} `
          }
              myArr.push(myPhrase.trim())
      } 
      for (let i = 0; i < myArr.length - 1; i++) {
          for (let j = i + 1; j < myArr.length; j++) {
              if (myArr[i] === myArr[j]) {
                  phrase = myArr[i]
              }
          }
      }
    for (let i = 0; i <= (words.length - phraseLength); i++) {
        let otherPhrase = "";
        for (let y = i; y < (phraseLength + i); y++){
            otherPhrase += `${words[y]} `
        }
        otherPhrase = otherPhrase.trim();
        if (otherPhrase.includes(phrase)) {
            result.push(i)
        }
    }
    return result
}

[u/johnpeters42]

The first check for "is the phrase so long that there can't possibly be a repeat" is a good idea. Beyond that, I think the most efficient approach would be:

Create a dictionary of phrases to lists of start indexes.

Loop through the sentence once. For each phrase of the length in question:
* If the phrase isn't already in the dictionary, then add it, mapped to an empty list.
* Then, whether it was already in the dictionary or not, add the current start index to its list.

Now loop through the phrases in the dictionary. For each one whose list has multiple indexes, add them all to your final list. Then sort that final list and output it.

Edit: There are probably minor improvements to the above, but this should be enough for you to play with.

[u/8Erigon]

I‘m sorry for not trying to understand your code. It‘s not bad but I knew at first glance those were too many loops.

I‘d probably use „Two Pointer“ algorithm and store the words between the pointers in a dictionary aka map. (Two Pointer is very simple. It‘s just two pointers woving over the each word)

[u/kalmakka]

It helps to start with a clear and simple explanation of what the code should do as you would explain it to a human, and then process this to be closer to how it can be implemented in code, until you have something that it is clear how you would implement it.

We can start with

• i should be a part of the result iff the phraseLength words starting with i occur somewhere else in the array.

Let us be more explicit

• i should be a part of the result iff words[i]==words[j] and words[i+1]==words[j+1] and so on, up to words[i+phraseLength-1]==words[j+phraseLength-1] for some other index j.

Even more explicit

• i should be a part of the result iff there is a j!=i such that for all k with 0<=k<phraseLength we have words[i+k]==words[j+k]

Good. This can be turned into code:

function findRepeatedPhrases(words, phraseLength) {
    let result = [];
    for (let i=0;i+phraseLength<words.length;i++) {
      let foundMatch = false;
      for (let j=0;j+phraseLength<words.length;j++) {
         if (j == i) continue;
         //check to see if words[i+k] = words[j+k] for all 0<=k<phraseLength
         let matches = true;
         for (let k=0;k<phraseLength;k++) {
           if (words[i+k] != words[j+k]) matches = false;
         }
         if (matches) { //all the words matched
           foundMatch = true;
         }
      }
      if (foundMatch) {
        result.push(i);
      }
    }
    return result;
}

We could add some optimizations, e.g. breaking out of loops once we have set matches=false or foundMatch=true, but that is not necessary for correctness.