Find the Duplicate Words in a Sentence - Java

Category: Medium | Concepts used: Word splitting, frequency counting, case-insensitivity

---

Problem Statement

Given a sentence, find all words that appear more than once.

Input : "the cat sat on the mat the cat ran"      Output: [the, cat]

Examples (with edge scenarios)

#	Input	Output	Why
1	"the cat sat on the mat the cat ran"	[the, cat]	Both repeat multiple times
2	"" (empty)	[]	No words at all
3	"unique words only here"	[]	No repeats
4	"The the THE" (case variations)	[the] (if case-insensitive) or [] (if case-sensitive)	Depends on whether case matters — clarify!
5	"Hi, there! Hi again." (punctuation attached)	Depends — "Hi," and "Hi" are different strings unless punctuation is stripped	Clarify: should punctuation be considered part of the word?

Common Fresher Mistake

Mistake	What happens	Fix
Not stripping punctuation before comparing words	"Hi," and "Hi" are treated as different words, missing real duplicates	Strip punctuation (e.g., using regex) before counting, if that’s the intended behavior
Not normalizing case	"The" and "the" counted as different words	Convert all words to lowercase before counting, if case-insensitivity is expected

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm how null and empty strings should behave, whether comparison is case-sensitive, and whether spaces or punctuation count. Java char values are UTF-16 code units, not always complete human-visible Unicode characters, so international text may require code points or grapheme-aware libraries.

Analogy: Sorting Envelopes in a Post Office

Imagine you are sorting a stack of handwritten letters:

• You first want to find addresses that received more than one letter:
  • Punctuation and Spacing (Normalizing): Some envelopes have commas, some have double spaces, and some write the city in all-caps while others write it in lowercase. Before sorting them, you rewrite every address on a clean sticky note in a standard format: all lowercase, with all punctuation stripped off.
  • The Pigeonholes (Frequency Map): You set up pigeonholes for each unique address. For every envelope, you drop it into its matching pigeonhole.
  • Identifying Duplicates (Filtering): At the end of the day, you walk around the pigeonholes. Any pigeonhole containing 2 or more envelopes is noted on your “duplicate deliveries” report!

---

Solution 1 — Split, Normalize, Count with Frequency Map (Recommended)

Intuition

This is a natural extension of the “count character occurrences” pattern (Q24), just applied to words instead of characters. Split the sentence into words, normalize each one (lowercase, strip punctuation) so equivalent words are recognized as the same, count occurrences in a map, then collect the ones whose count exceeds 1.

import java.util.*;

public class DuplicateWords {
    public static List<String> findDuplicates(String sentence) {
        // normalize: lowercase, then split on non-letter characters (handles punctuation & spacing)
        String[] words = sentence.toLowerCase().split("[^a-zA-Z']+");

HashMap<String, Integer> freq = new HashMap<>();
        for (String word : words) {
            if (!word.isEmpty()) {
                freq.put(word, freq.getOrDefault(word, 0) + 1);
            }
        }

List<String> duplicates = new ArrayList<>();
        for (var entry : freq.entrySet()) {
            if (entry.getValue() > 1) {
                duplicates.add(entry.getKey());
            }
        }
        return duplicates;
    }

public static void main(String[] args) {
        System.out.println(findDuplicates("the cat sat on the mat the cat ran"));
        // [the, cat] (order may vary since HashMap doesn't guarantee order)

System.out.println(findDuplicates("Hi, there! Hi again."));
        // [hi]

System.out.println(findDuplicates("unique words only here"));
        // []
    }
}

Output:

[the, cat]
[hi]
[]

Dry Run (sentence = “Hi, there! Hi again.”)

Lowercased: "hi, there! hi again."
Split on non-letters: ["hi", "there", "hi", "again"]

freq = {hi:2, there:1, again:1}

Scanning entries: hi has count 2 > 1 -> added to duplicates

Final: [hi]

Interviewer’s take

This is the expected solution — the key insight is normalizing the words (lowercase + strip punctuation) before counting, since real sentences are messy. Interviewers specifically test whether candidates think about this normalization step rather than naively splitting on spaces alone.

Follow-up questions you might get:

• “What if case sensitivity matters (e.g., proper nouns should be treated differently)?” → Skip the .toLowerCase() step, and clarify this assumption with the interviewer up front.
• “How would you preserve the original order of first appearance in the output?” → Use a LinkedHashMap instead of HashMap.
• “What regex are you using, and why?” → "[^a-zA-Z']+" splits on any run of characters that are NOT letters or apostrophes (to keep contractions like "don't" intact) — this naturally strips out punctuation, extra spaces, etc.

---

📊 Visual Flowchart

graph TD
    Start["Input Sentence"] --> Lower["Convert to Lowercase"]
    Lower --> RegexSplit["Split by Regex: [^a-zA-Z']+"]
    RegexSplit --> InitMap["Initialize freqMap"]
    InitMap --> LoopWords{"For each word"}
    LoopWords -->|Is Empty| SkipWord["Skip"]
    LoopWords -->|Not Empty| TrackWord["freqMap[word]++"]
    SkipWord --> LoopWords
    TrackWord --> LoopWords
    LoopWords -->|Done| Filter["Filter entries where count > 1"]
    Filter --> End["Return duplicate list"]

---

Final Verdict — Which Solution Should You Give?

• Solution 1 is the standard, expected approach — this problem doesn’t really have a meaningfully “worse” naive alternative worth presenting separately; the frequency-map pattern is the natural and correct solution from the start.
• The real differentiator interviewers look for is proactively normalizing case and punctuation, and clearly stating those assumptions.

---

Quick Recap

Approach	Time	Space	Interview Signal
Split + normalize + frequency map	O(n)	O(n)	Standard, correct — normalization is the key detail