235. Find the First Repeated Word in a String

Given a sentence of space-separated words, find the first word (scanning left to right) that has already appeared earlier in the sentence. Print that word, or print 'None' if no word repeats. Comparison is case-sensitive and exact.

Input: The input is a single line containing a sentence of space-separated words. Output: Print the first word (by scan order) that repeats, or print 'None' if no word repeats.

1 <= number of words <= 10^5, 1 <= |each word| <= 50, words consist of English letters only

This problem is exact-match and case-sensitive per its statement - 'The' and 'the' would be treated as different words, worth confirming explicitly if the exact rules are ever ambiguous.

Scan a sentence word by word and find the first word that shows up again, having already appeared earlier. Brute force: For every word, scan all the words BEFORE it directly to check for a match - this costs O(n²) in the number of words, unnecessary when a running seen-set does the same job in one pass. Optimised: A hash set built incrementally as you scan lets you check 'have I seen this word already' in O(1) at each step, so the very first true repeat is found in a single linear pass, with no need to compare against every earlier word individually.

Scan the words left to right, and for each word, look back through every word that came before it checking for an exact match; the first word (in left-to-right order) for which such a match is found is the answer. This directly matches the problem's definition of 'first word that has already appeared earlier', but comparing every word against all of its predecessors makes it quadratic in the number of words. Time: O(n^2) Space: O(1) extra (excluding input)

Scan the words left to right exactly once, keeping a hash set of words already seen. For each word, check whether it's already in the set (an O(1) average lookup); the first word for which this check succeeds is immediately the answer, since scanning strictly left to right guarantees the very first repeat encountered this way is the first repeat overall. If no word ever triggers a hit, no word repeats. This finds the answer in a single linear pass with no sorting or nested comparisons at all. Time: O(n) Space: O(n)

Pair every word with its original position and sort these pairs by word (so identical words become adjacent), which lets duplicate words be found by a single linear scan over the sorted list rather than a nested comparison. For every group of matching words, the position of interest is the second-smallest original index in that group (the point at which the word was first seen to repeat); taking the minimum such second-occurrence index across all duplicate groups gives the first word to repeat in the original left-to-right sense. Sorting trades the quadratic comparisons for an n log n sort. Time: O(n log n) Space: O(n)

1. Split the sentence into words. 2. Scan the words left to right, keeping a set of every word already seen. 3. The very first word that's already in the set is your answer - stop immediately, don't look for a 'more repeated' word. 4. If you finish scanning without hitting a repeat, no word repeats at all.

Time: O(total characters across all words) - one linear pass, with instant hash-set lookups. Space: O(number of distinct words), for the seen-set.

A sentence with no repeated words at all ('None'); a word repeating more than twice, where only the first repetition point matters; case-sensitive comparison; up to 10^5 words for performance.

Be precise that you must stop at the FIRST word that repeats when scanning left to right - not the word that repeats the MOST, which is a subtly different (and much easier to get wrong) question.