Find the first repeated word in string

The problem, simply

You get a sentence of words separated by spaces. Read it from left to right. Give back the first word that you meet for the second time. If no word repeats, say so (here we return an empty string).

Below, n is the number of words and w is the length of the longest word.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each word, look back at all the words before it. The first word that finds an equal word behind it is the answer.

1. Split the sentence into words.
2. For j = 1, 2, ...: compare words[j] with every words[i] where i < j.
3. The first j with a match gives the answer.

class Solution {
    public String firstRepeated(String s) {
        String[] words = s.trim().split("\\s+");
        for (int j = 1; j < words.length; j++) {
            for (int i = 0; i < j; i++) {
                if (words[i].equals(words[j])) return words[j];   // met it before
            }
        }
        return "";   // no word repeats
    }
}

How long it takes: about n^2 / 2 pairs of words, and comparing two words takes up to w steps, so O(n^2 * w). Extra room: the array of words, O(n * w).

Way 2: the clever way

Use the basket from the story. In code it is a hash set: you can ask "is this word inside?" in about the time it takes to read the word.

1. Split the sentence into words.
2. For each word in order: if it is already in the set, return it.
3. Otherwise add it to the set.
4. If the loop ends, return the empty string.

import java.util.*;

class Solution {
    public String firstRepeated(String s) {
        Set<String> seen = new HashSet<>();
        for (String word : s.trim().split("\\s+")) {
            if (!seen.add(word)) return word;   // add() says false when the word was already there
        }
        return "";
    }
}

How long it takes: each word is hashed and looked up once, O(w) each, so O(n * w), which is the size of the sentence. Extra room: the set may hold every word, O(n * w).

Another way: the other meaning

Some versions of this problem mean something else by "first repeated word": the word that appears earliest in the sentence among all the words that repeat somewhere. For he had had he that is he, because he starts the sentence and also appears later.

For that meaning, count every word first, then walk the words again and return the first one whose count is more than 1.

import java.util.*;

class Solution {
    public String firstRepeated(String s) {
        String[] words = s.trim().split("\\s+");
        Map<String, Integer> count = new HashMap<>();
        for (String word : words) count.merge(word, 1, Integer::sum);   // count everything first
        for (String word : words) {
            if (count.get(word) > 1) return word;                     // earliest word that repeats
        }
        return "";
    }
}

This also takes O(n * w) time and room, but it must read the whole sentence before answering.

Watch out for

• Splitting on a single space " " breaks on double spaces and gives empty words. Use trim() and split("\\s+").
• Compare words with equals, never ==. Two equal words from split are different objects.
• Case and punctuation: Had and had, are different strings. If they should match, lowercase the sentence and strip punctuation first.

What interviewers ask next

• What if the text is a huge stream you cannot hold in memory? Keep only the set, read word by word, and stop at the first hit. If even the set is too big, a Bloom filter answers "maybe seen" in tiny room, with a second check for the maybes.
• Can a trie replace the set? Yes. Insert each word letter by letter and mark where words end. Reaching an end mark means a repeat. Words that share a start share nodes, which can save room.
• First non repeated word? Count every word, then walk again and return the first word with count 1.
• Most common word, ignoring a list of banned words (LeetCode 819)? Lowercase, strip punctuation, count with a map while skipping banned words, then take the biggest count.

Remember this

Grown-up words: the basket is a hash set, seen.add returning false is a membership test, counting words uses a hash map of frequencies, and w is the cost of hashing a word.