First Duplicate Character in a String

Problem

Given a string (or array), find the first character (or element) that repeats (i.e., appears more than once). Return the first such character in order of appearance. If no character repeats, return a suitable message.

Examples

Example 1

Input: "learnwithk5kc"
Output: 'k'
Explanation: The character `k` appears more than once (first at index 9, 0-based) in `learnwithk5kc`, so 'k` is the first repeating character.

Example 2

Input: "algorithms"
Output: No repeating character found.
Explanation: All characters are unique.

Solution

Method 1 – Brute Force

Intuition

Check each character and see if it appears again later in the string.

Approach

1. For each character, scan the rest of the string to see if it repeats.
2. Return the first character that repeats.

Complexity

• ⏰ Time complexity: O(n²) — Each character may be compared with all others.
• 🧺 Space complexity: O(1) — No extra space used.

Method 2 – Hash Map

Intuition

Count occurrences of each character, then find the first character with count > 1.

Approach

1. Traverse the string and count occurrences of each character using a hash map or array.
2. Traverse the string again, and for each character with count > 1, return it.
3. If none found, return null or a suitable message.

Code

Java

public class Solution {
    public Character getFirstRepeating(String input) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for (int i = 0; i < input.length(); i++) {
            if (map.get(input.charAt(i)) > 1) {
                return input.charAt(i);
            }
        }
        return null;
    }
}

Python

class Solution:
    def get_first_repeating(self, s: str) -> str:
        count = {}
        for ch in s:
            count[ch] = count.get(ch, 0) + 1
        for ch in s:
            if count[ch] > 1:
                return ch
        return ''

Complexity

• ⏰ Time complexity: O(n) — Each character is processed twice.
• 🧺 Space complexity: O(n) — Space for the hash map.