First Non-Repeating Character

Tags

First Non-Repeating Character

Category

Strings

Difficulty

Easy

Problem Statement

Given a string, find the index of the first character that does not repeat anywhere else in the string. If no such character exists, return -1.

Intuition

A non-repeating character is one whose frequency in the entire string is exactly 1. By first counting every character's frequency and then scanning the string from left to right, the first character with a frequency of 1 is our answer. The two-pass approach ensures we have complete frequency information before making a decision.

Approach

  1. Build a frequency map by iterating through the entire string and counting occurrences of each character.
  2. Iterate through the string a second time from left to right.
  3. For each character, check its frequency in the map.
  4. Return the index of the first character whose frequency is 1.
  5. If no such character is found, return -1.

Pseudocode

function firstNonRepeatingCharacter(string):
    freq = {}

    for char in string:
        freq[char] = freq.getOrDefault(char, 0) + 1

    for i from 0 to length(string) - 1:
        if freq[string[i]] == 1:
            return i

    return -1

Time & Space Complexity

  • Time: O(n) where n is the length of the string. Two passes through the string, each O(n).
  • Space: O(c) where c is the number of unique characters. For a fixed alphabet (e.g., 26 lowercase letters), this is O(1).

Key Insights

  • Two passes are necessary: the first to gather full frequency data, the second to find the first character with frequency 1.
  • A single-pass approach using an ordered map or linked hash map is possible but adds implementation complexity without improving asymptotic performance.
  • The order of the second pass matters: we scan left to right to find the first non-repeating character.

Edge Cases

  • Empty string: return -1.
  • All characters are unique: return 0 (the first character).
  • All characters are the same: return -1.
  • The non-repeating character is at the very end of the string.
  • String of length 1: return 0.

Linked mentions