Find the First Non-Repeating Character in a String

The first non-repeating character in teeterson is r: t appears twice, e appears three times, but r appears only once. Finding this in O(n) time rather than O(n²) is the standard expectation in placement coding rounds.

What “First Non-Repeating” Means

A character is non-repeating if it appears exactly once in the string. The problem asks for the character at the smallest index that satisfies this condition.

Two sample cases:

• Input: teeterson → Output: r
• Input: charactercharacter → Output: All characters are repetitive

Verifying teeterson position by position:

• t is at positions 0 and 3. Repeating.
• e is at positions 1, 2, and 4. Repeating.
• r is at position 5 only. First non-repeating character.

The second sample, charactercharacter, is the string character written twice. Every character appears exactly twice, so no non-repeating character exists and the expected output is the sentinel message.

LeetCode 387 is the canonical version of this problem. It constrains input to lowercase English letters and asks for the index of the first unique character rather than the character itself. Campus placement rounds often present the same underlying logic with slightly different input and output formats.

Brute Force: Two Nested Loops

For each character at position i, scan every other position j in the string and check whether s[i] == s[j]. If no match is found anywhere, s[i] is the answer. If a match is found, move on to i + 1.

def first_non_repeating_brute(s):
    n = len(s)
    for i in range(n):
        found = False
        for j in range(n):
            if i != j and s[i] == s[j]:
                found = True
                break
        if not found:
            return s[i]
    return "All characters are repetitive"

print(first_non_repeating_brute("teeterson"))           # r
print(first_non_repeating_brute("charactercharacter"))  # All characters are repetitive

Time complexity: O(n²). Space complexity: O(1).

The approach is correct and easy to follow, which makes it a reasonable starting answer during a verbal walkthrough. The problem is performance. For every character in the string, the inner loop re-scans the entire string. AMCAT Automata and other placement coding platforms enforce strict per-case time limits; an O(n²) solution will get a Time Limit Exceeded verdict once the string is long enough.

The improvement is to avoid rescanning on every iteration by storing the frequency information up front.

Hash Map: The O(n) Solution

The standard approach uses a frequency dictionary in exactly two passes over the string:

• Pass 1: count how many times each character appears.
• Pass 2: scan left to right and return the first character whose count equals 1.

Python

def first_non_repeating(s):
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    for ch in s:
        if freq[ch] == 1:
            return ch
    return "All characters are repetitive"

print(first_non_repeating("teeterson"))           # r
print(first_non_repeating("charactercharacter"))  # All characters are repetitive

After pass 1 on teeterson, the dictionary is {'t': 2, 'e': 3, 'r': 1, 's': 1, 'o': 1, 'n': 1}. Pass 2 visits t (count 2), e (3), e (3), t (2), e (3), r (1) and returns r at the sixth position.

Note that the second loop iterates over the original string, not over the dictionary. This preserves left-to-right order. If you iterated over the dictionary keys instead, Python’s insertion-order guarantee would give the same result in Python 3.7+, but iterating the string is the intent-clearer choice and works in all Python versions.

This is structurally similar to other hash-based problems like finding all symmetric pairs in an array, where the hash map reduces a nested comparison to two linear scans.

C

#include <stdio.h>
#include <string.h>

char firstNonRepeating(char s[]) {
    int freq[256] = {0};
    int n = (int)strlen(s);
    int i;
    for (i = 0; i < n; i++)
        freq[(unsigned char)s[i]]++;
    for (i = 0; i < n; i++)
        if (freq[(unsigned char)s[i]] == 1)
            return s[i];
    return '\0';
}

int main() {
    char s[1000];
    scanf("%999s", s);
    char result = firstNonRepeating(s);
    if (result == '\0')
        printf("All characters are repetitive\n");
    else
        printf("%c\n", result);
    return 0;
}

The C version uses an integer array of size 256 indexed by ASCII value instead of a hash map. No dynamic memory allocation is needed. The cast to unsigned char prevents negative indices on systems where char is signed.

Java

import java.util.*;

public class FirstNonRepeating {
    public static char firstNonRepeating(String s) {
        Map<Character, Integer> freq = new LinkedHashMap<>();
        for (char c : s.toCharArray())
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        for (char c : s.toCharArray())
            if (freq.get(c) == 1)
                return c;
        return '\0';
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        char result = firstNonRepeating(s);
        if (result == '\0')
            System.out.println("All characters are repetitive");
        else
            System.out.println(result);
    }
}

LinkedHashMap preserves insertion order, but the second loop still iterates over the original string rather than the map. This keeps the logic explicit and independent of map implementation details.

Complexity Comparison

Approach	Time	Space	Notes
Nested loops	O(n²)	O(1)	No extra allocation; slow on large inputs
Hash map	O(n)	O(k)	Two passes; k = distinct character count

k is the number of distinct characters in the string. For lowercase English letters, k is at most 26. For full ASCII, k is at most 128. Because k is bounded by the alphabet size rather than the input length, the hash map’s extra space is effectively constant for constrained inputs.

Understanding space complexity trade-offs matters when making this choice. O(k) auxiliary space where k is alphabet-bounded differs from O(n) where space scales with input size. Interviewers at product companies will sometimes follow up with the space complexity question specifically to test this distinction.

Variations and Edge Cases

The two-pass logic handles most variants without structural change.

Single character: any string of length 1 has exactly one character with frequency 1. Pass 2 returns it immediately.

Case sensitivity: 'A' and 'a' are treated as different characters by default in all three implementations above. For case-insensitive matching, call .lower() in Python or Character.toLowerCase() in Java before building the frequency map.

Empty string: pass 2 never executes. Add an explicit guard if the problem requires a specific return value for an empty input.

Unicode input: the Python dict and Java HashMap handle arbitrary Unicode without changes. The C array of size 256 covers only ASCII; extend to a hash map for Unicode support.

Problems like finding the equilibrium index of an array follow the same two-pass template: compute a running aggregate on pass 1, then answer the primary query in O(1) per element on pass 2. Recognising this pattern saves time when a new problem fits the same shape.

GeeksforGeeks covers stream-based variants and additional edge cases for this problem, including maintaining a running first non-repeating character as characters arrive one at a time.

The freq dictionary from the hash map solution above is, at scale, the same structure used at the start of most text-processing pipelines. Frequency counting is how bag-of-words representations are built before feeding text into a large language model. If you want to build those kinds of NLP pipelines on top of LLMs rather than practise placement problems, TinkerLLM is a practical entry point at ₹299.