Find the First Repeating Character in a String - Java

Category: Medium | Concepts used: Frequency map, first-seen tracking

---

Problem Statement

Given a string, find the first character that repeats (appears more than once), scanning left to right.

Input : "swiss"      Output: 's'   ('s' appears at index 0 and repeats later)

Note: “first repeating character” means the first character (by position) that has a duplicate somewhere in the string — this is subtly different from “first non-repeating character” (Q48/44), so read carefully!

Examples (with edge scenarios)

#	Input	Output	Why
1	"swiss"	's'	's' (at index 0) repeats later at index 3
2	"abcabc"	'a'	'a' is the first character (by position) that has a duplicate anywhere
3	"" (empty)	None	No characters at all
4	"abcdef" (no repeats)	None	Every character is unique
5	"aabbcc"	'a'	First position with a repeat is index 0 ('a', which repeats at index 1)

Common Fresher Mistake

Mistake	What happens	Fix
Confusing “first repeating” with “first character to repeat AGAIN” (i.e., returning the second occurrence’s position/character instead of clarifying)	Ambiguous — but conventionally, “first repeating character” means the earliest character (by its first position) that has any duplicate	Clarify definition with the interviewer if in doubt
Using nested loops (checking each character against all others)	O(n²) — works but not efficient	Prefer a frequency-map-based single pass, O(n)

---

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: The Hotel Guest Clipboard

Imagine you are a hotel receptionist checking in guests arriving in a line:

• Solution 1 (The Stalker): Every time a guest steps up, you run outside and search the entire remaining line to see if they are standing out there again. If you find their duplicate, you immediately shout: “This person is a repeating guest!” This is very slow and rude.
• Solution 2 (The Tally Sheet):
  • As guests arrive, you check them in one-by-one and mark a tick count next to their name on a clipboard (Pass 1 - building the frequency map).
  • Once the line is empty and you have counted everyone, you look back at the checked-in guest records in the order they originally arrived (Pass 2 - scanning).
  • The first guest’s name you see that has a tally mark greater than 1 is declared the first repeating guest!

---

Solution 1 — Brute Force with Nested Loops

Intuition

For each character (starting from the left), check whether it appears again anywhere later in the string. The first character for which this is true is the answer.

public class FirstRepeatingBruteForce {
    public static Character firstRepeating(String str) {
        for (int i = 0; i < str.length(); i++) {
            for (int j = i + 1; j < str.length(); j++) {
                if (str.charAt(i) == str.charAt(j)) {
                    return str.charAt(i); // found a duplicate for this character
                }
            }
        }
        return null; // no repeating character found
    }

public static void main(String[] args) {
        System.out.println(firstRepeating("swiss")); // s
        System.out.println(firstRepeating("abcdef")); // null
    }
}

Output:

s
null

Dry Run (str = “swiss”)

i=0('s'): j=1('w')no, j=2('i')no, j=3('s') MATCH! -> return 's'

Interviewer’s take

Correct, but O(n²) — inefficient for longer strings. A good opening answer, but expect to be asked for an optimization.

Follow-up questions you might get:

• “Can you find this in a single pass, O(n)?” → leads to Solution 2.

---

Solution 2 — Using a Frequency Map (Two Passes, O(n), Recommended)

Intuition

First, count how many times every character appears across the whole string (we need this “global” knowledge before we can know if a character repeats). Then, in a second pass, walk through the string in order and return the first character whose total count is greater than 1 — this guarantees we find the earliest-positioned character that has a duplicate anywhere.

import java.util.HashMap;

public class FirstRepeatingFreqMap {
    public static Character firstRepeating(String str) {
        HashMap<Character, Integer> freq = new HashMap<>();

// Pass 1: build frequency counts
        for (char ch : str.toCharArray()) {
            freq.put(ch, freq.getOrDefault(ch, 0) + 1);
        }

// Pass 2: find the first character (in order) with count > 1
        for (char ch : str.toCharArray()) {
            if (freq.get(ch) > 1) {
                return ch;
            }
        }
        return null; // no repeats found
    }

public static void main(String[] args) {
        System.out.println(firstRepeating("swiss"));  // s
        System.out.println(firstRepeating("abcabc")); // a
        System.out.println(firstRepeating("abcdef"));  // null
    }
}

Output:

s
a
null

Dry Run (str = “swiss”)

Pass 1 - freq map:
freq = {s:2, w:1, i:1}

Pass 2 - scan in order:
's' -> freq.get('s')=2 > 1 -> return 's'  (immediately, first match)

Interviewer’s take

This is the preferred final answer — O(n) time overall (two linear passes), using the classic “count first, then scan” pattern that’s reused across many similar string problems. Clean and efficient.

Follow-up questions you might get:

• “Why do you need two passes instead of one?” → The very first pass through the string can’t yet know if a character will repeat later — you need the complete counts before you can correctly identify the first confirmed repeat.
• “How is this different from finding the first NON-repeating character?” → Same two-pass pattern, just flip the condition from count > 1 to count == 1 (see the separate “first non-repeating character” problem).

---

📊 Visual Flowchart

graph TD
    Start["Input String str"] --> Pass1["Pass 1: Count Frequencies"]
    Pass1 --> Loop1{"i < str.length?"}
    Loop1 -->|Yes| MapInc["freqMap[str[i]]++"]
    MapInc --> Next1["i++"]
    Next1 --> Loop1
    Loop1 -->|No| Pass2["Pass 2: Scan for repeaters"]
    Pass2 --> Loop2{"j < str.length?"}
    Loop2 -->|Yes| CheckFreq{"freqMap[str[j]] > 1?"}
    CheckFreq -->|Yes| RetChar["Return str[j]"]
    CheckFreq -->|No| Next2["j++"]
    Next2 --> Loop2
    Loop2 -->|No| RetNull["Return null"]

---

Final Verdict — Which Solution Should You Give?

Solution 1 (nested loops)  ──O(n²)──►  Fine to start, but improve when asked
Solution 2 (frequency map, two passes)  ──O(n)──►   PREFERRED FINAL ANSWER

• Solution 2 is the expected final answer — efficient and follows a widely reusable pattern.

---

Quick Recap

Approach	Time	Space
Nested loops	O(n²)	O(1)
Frequency map (two passes)	O(n)	O(k) — k = distinct characters