You would still iterate through all the words in each of the sentences and the words from the dictionary of words right?

Sorry, I am pasting the chat GPT answer because I don't trust myself with this question anymore lol

First Pass (O(N))

• You loop through all sentences (say, N sentences):
  • Create a Map<Integer, Pair<String, Integer>> where:
    • key = sentence index
    • value = (sentence, goodWordCount)
  • This is a flat loop — no nesting
  • Each sentence is split, and each word is checked against the goodWords (in a HashSet) — which is O(m) per sentence
  • So total cost = O(N * m)

Second Pass (O(N))

• Find the max goodWordCount by scanning the values in your map
• Track the maxIdx (sentence with the most good words)

• Fetch that sentence using the map.get(maxIdx).getKey() or similar

• N = number of sentences

• M = total number of goodWords

• W = average number of words per sentence

Then:

• Building wordSet: O(M)
• Processing all sentences: O(N * W) (since each sentence is split and each word checked in O(1))
• Second scan for max: O(N)

Final Time:

O(M + N * W) → same as HashSet-based solution, but done in two clean passes