First Unique Character in a String Algorithm

The first unique character problem requires identifying the first character that appears exactly once in a string. This classic algorithmic challenge tests understanding of hash tables, array indexing, and optimal time complexity trade-offs in string processing scenarios.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the expected input size range? (e.g., string length up to 10^5?)
2. Are we guaranteed that the input contains only lowercase letters, or could it contain any ASCII characters?
3. Should we return the index of the first unique character, or just indicate whether one exists?
4. Can we modify the input string, or must we work with a copy?
5. What should we return if there are no unique characters? (e.g., -1 or null?)

Restatement in my own words: Given a string, I need to find the index of the first character that appears exactly once in the string. If no such character exists, I should return -1.

Clarification of inputs, outputs, and constraints:

• Input: A string s containing only lowercase English letters (per typical constraints, though this should be confirmed)
• Output: Integer representing the 0-based index of the first unique character, or -1 if none exists
• Constraints:
  • String length can be up to 10^5 (this is a key constraint that affects algorithm choice)
  • Characters are limited to lowercase English letters (a-z)

Assumptions I'm making:

• The input string contains only lowercase English letters (a-z) as is typical in such problems
• We want to return the 0-based index of the first unique character, or -1 if none exists
• The input string can be read but not modified (we're not asked to mutate it)

Data shape and hidden structure: The problem involves a linear sequence of characters where we need to track character frequencies. The key insight is that we're looking for a character with frequency exactly 1, and among all such characters, we want the one that appears earliest in the string. This suggests we need to process the string twice: once to count frequencies, and once to find the first character with frequency 1.

The problem has a hidden structure where:

• We need to identify unique elements in order (first occurrence)
• The solution space is bounded by character set size (26 lowercase letters)
• We're essentially looking for a "first in order" element that meets a specific condition (frequency = 1)

2. Pattern Recognition

Identifying the pattern

The most likely pattern here is frequency counting with single-pass scanning. This is a classic string processing problem that maps directly to the "count occurrences" pattern.

Wording that signals the pattern

• "First unique character" - signals we need to track character frequencies and identify which one appears exactly once
• "in a string" - indicates we're working with a linear sequence of characters
• The requirement for "first" suggests we need to process elements in order and maintain that ordering information

Why this fits the pattern

This problem requires us to:

1. Count occurrences of each character in the string (frequency counting)
2. Find the first character that appears exactly once (ordered processing)
3. Return its index position

The key insight is that we need to make two passes through the data: one to count frequencies, and another to find the first unique character. This is a textbook case of the "two-pass frequency counting" pattern.

Core insight

The problem asks for the first unique character, which means we must preserve the original order of characters. This tells us that we need to process the string in sequence and track character counts while maintaining their relative positions.

The pattern is fundamentally about frequency analysis with ordering preservation - we're not just counting characters, but identifying which character appears exactly once and doing so in the earliest possible position.

This pattern commonly appears in problems like:

• Finding first non-repeating character
• Validating anagrams with position constraints
• Processing sequences where element uniqueness matters in order

The solution will likely involve either:

1. A frequency map with ordered traversal, or
2. Two-pass approach with character position tracking

This is a linear scan with frequency tracking pattern that's very common in FAANG interviews.

3. Approach Evolution

My first instinct is to use a brute force approach where I check each character's occurrence count by scanning the entire string for every character. But that's O(n²) because for each of the n characters, I'm doing an O(n) scan to count occurrences. Let me think about how to optimize this.

I notice that if I can preprocess the string once to count all character frequencies, then I can make a second pass to find the first character with frequency 1. This reduces it to O(n) time by using a hash map to store character counts.

The key insight is that I need to process the string twice: once for counting and once for finding the first unique character. The invariant I must maintain is that during the second pass, I'm looking for the first character whose count in my frequency map equals exactly 1.

Let me think about this more carefully. The first pass builds a frequency map, and the second pass maintains the order of characters as they appear in the original string. Since we're looking for the first unique character, I need to preserve the original order in my frequency tracking.

Actually, I can do even better with a single pass through the string using a more sophisticated data structure that maintains both frequency and first occurrence index. But let me stick with the clean O(n) two-pass approach for now - it's clear, correct, and easy to reason about.

The optimization comes from recognizing that I don't need to re-scan the entire string for each character, but rather can build up all the necessary information in one pass and then use that information to find my answer in a second pass.

My approach will be:

1. First pass: Count frequency of each character using HashMap
2. Second pass: Iterate through the string and return first character with frequency 1

This is O(n) time and O(k) space where k is the number of unique characters (at most 26 for lowercase letters). The solution is optimal because we must read each character at least once to determine uniqueness.

The invariants that must hold:

• During first pass, frequency map contains correct counts for all characters
• During second pass, we return the first character that appears exactly once in the original string

4. Data Structure Choice

For this problem, I'll use a HashMap as my primary data structure to store character frequencies.

Primary Data Structures Used

1. HashMap<Character, Integer> - to store each character's frequency count
2. StringBuilder (optional) - to build the result string

Why Each Data Structure Is Needed

The HashMap is essential because:

• It provides O(1) average time complexity for both insertion and lookup operations
• It naturally handles the frequency counting requirement
• It allows us to efficiently track which characters appear exactly once

The StringBuilder is used for efficient string building when constructing the result, though it's not strictly necessary for the core algorithm.

Time and Space Impact

• Time Complexity: O(n) for building the frequency map, where n is string length
• Space Complexity: O(k) where k is the number of unique characters (at most 26 for lowercase letters)
• In worst case with all unique characters, space is O(n) but typically much smaller

Helper Structure for Simplification

I'm not using any additional helper structures beyond the HashMap. The solution can be implemented with just the frequency map and a single pass through the string.

The HashMap approach is optimal here because:

• It eliminates the need for multiple passes through the string
• It provides direct access to character counts without sorting or additional preprocessing
• It scales linearly with input size and handles variable character sets gracefully

5. Algorithm Walkthrough

Let me trace through the algorithm with the example string "leetcode":

Step 1: Initialize frequency map

• Map is empty: {}
• We'll process each character and build the frequency count

Step 2: First pass - populate frequency map

• Process 'l': freqMap['l'] = 1
• Process 'e': freqMap['e'] = 1
• Process 'e': freqMap['e'] = 2
• Process 't': freqMap['t'] = 1
• Process 'c': freqMap['c'] = 1
• Process 'o': freqMap['o'] = 1
• Process 'd': freqMap['d'] = 1
• Process 'e': freqMap['e'] = 3

Final frequency map: {'l':1, 'e':3, 't':1, 'c':1, 'o':1, 'd':1}

Step 3: Second pass - find first unique character

• Index 0: 'l' has frequency 1 → return 0

The algorithm correctly identifies index 0 as the answer.

Edge case handling:

• For input "aabb", we'd build frequency map {'a':2, 'b':2}
• Second pass would check each character: 'a' has freq 2, 'a' has freq 2
• No unique characters found → return -1

Why termination is guaranteed: The algorithm always terminates because we either find a unique character (return index) or process all characters and return -1. The second pass is guaranteed to examine every character in the string exactly once, making it deterministic and complete.

6. Java Solution

public class FirstUniqueCharacter {
    public int firstUniqChar(String s) {
        // Handle edge case of empty string
        if (s == null || s.length() == 0) {
            return -1;
        }
        
        // Array to store frequency of each character (assuming only lowercase letters)
        int[] charCount = new int[26];
        
        // First pass: count frequency of each character
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            charCount[c - 'a']++;
        }
        
        // Second pass: find first character with count of 1
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (charCount[c - 'a'] == 1) {
                return i;
            }
        }
        
        // No unique character found
        return -1;
    }
}

This solution uses a two-pass approach with a fixed-size array for character counting. The first pass builds a frequency map, and the second pass identifies the first unique character by checking each position against the frequency counts. The solution handles all edge cases including empty strings and returns -1 when no unique character exists.

The key insight is that we can use the array index as a mapping from characters to their frequency counts, since we're dealing with only lowercase English letters (a-z). This allows us to avoid using a HashMap and achieve better constant-time access to character frequencies.

7. Complexity Analysis

Time Complexity: O(n) where n is the length of the input string. The algorithm makes exactly two passes through the string: one to count character frequencies and another to find the first unique character. Both passes are linear operations, so the overall time complexity is O(n).

Space Complexity: O(1) in terms of auxiliary space. The HashMap used to store character frequencies has at most 26 entries (for lowercase English letters). Since this upper bound is constant and independent of input size, the space complexity is considered O(1). However, if we consider the actual memory usage including the input string itself, it would be O(n) for the input storage and O(1) for the frequency map.

The solution is optimal because:

• We must examine each character at least once to determine uniqueness
• The frequency counting approach is the most efficient way to track character occurrences
• No better data structure exists for this specific problem that would reduce the time complexity below O(n)

The linear time complexity is necessary since we need to process all characters to establish their uniqueness status, and the constant space usage for character frequency tracking is optimal given that we're dealing with a fixed character set (26 lowercase letters).

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty string: Returns -1 as expected, but requires explicit handling to avoid index errors
• Single character: Returns 0 if it's unique, or -1 if it's a duplicate
• Two characters: Properly handles both cases where one or both are unique

Duplicate Values and Repeated States

• All duplicate characters: Returns -1 correctly, but the algorithm still processes all characters
• Multiple unique characters: Correctly identifies the first occurrence, not just any unique character
• Repeated character patterns: Handles cases like "aabbcc" vs "abccba" appropriately

Boundary Conditions

• First character is unique: Algorithm correctly identifies position 0
• Last character is unique: Properly handles the end of string boundary
• String with only one unique character: Returns correct index position

Common Implementation Mistakes

• Incorrect indexing: Using charAt(i) instead of proper bounds checking in loops
• Not resetting counters properly: When using frequency arrays, ensuring all positions are initialized to 0
• Misunderstanding return value: Confusing -1 (no unique) with 0 (first position)
• Off-by-one errors: Loop bounds that exclude the last character or include beyond string length
• Using wrong data structure: Using HashMap instead of fixed-size array for ASCII characters when the problem allows it

Implementation-specific Pitfalls

• Integer overflow in frequency counting: Though unlikely with string constraints, could be an issue for very large inputs
• Not handling non-ASCII characters: If the problem allows Unicode, array-based approaches fail
• Unnecessary object creation: Creating new collections when simple arrays suffice for ASCII characters

The solution must carefully handle all these edge cases to maintain correctness across the full spectrum of valid inputs.

9. Alternative Approaches

There are several alternative approaches to solving this problem, each with different trade-offs:

Approach 1: Brute Force with indexOf/lastIndexOf Instead of counting frequencies, we could iterate through each character and use indexOf() and lastIndexOf() to check if the character appears only once. For each character at position i, we check if indexOf(char) == lastIndexOf(char). This approach has O(n²) time complexity because for each character, we potentially scan the entire string again.

Approach 2: HashMap with Single Pass We can use a HashMap to store character frequencies, but instead of two passes, we process the string once and maintain a queue or list of unique characters in order. When we encounter a character that's already been seen, we remove it from our tracking structure. This approach is still O(n) time but uses additional space for the tracking structure.

Approach 3: Array-based Counting (for lowercase letters only) If we're guaranteed that the string contains only lowercase English letters, we can use a fixed-size array of size 26 instead of a HashMap. This reduces space complexity from O(k) where k is the number of unique characters to O(1), and provides faster access due to direct indexing.

Trade-offs:

• The HashMap approach is most general and handles any character set, but has higher space overhead
• The array approach is optimal for constrained character sets but not flexible
• The brute force approach has the simplest logic but poor time complexity
• Our chosen solution strikes the best balance of generality, efficiency, and readability

The key insight is that while we could optimize for specific constraints (like only lowercase letters), the general solution using HashMap provides the most maintainable and scalable approach for real-world applications.

10. Test Cases

public class FirstUniqueCharacterTest {
    public static void main(String[] args) {
        // Test case 1: Basic example from problem
        // Input: "leetcode" -> Output: 0 (first 'l' at index 0)
        System.out.println("Test 1: " + firstUniqChar("leetcode")); // Expected: 0
        
        // Test case 2: All characters are unique
        // Input: "abcdef" -> Output: 0 (first 'a' at index 0)
        System.out.println("Test 2: " + firstUniqChar("abcdef")); // Expected: 0
        
        // Test case 3: No unique characters
        // Input: "aabb" -> Output: -1 (no unique chars)
        System.out.println("Test 3: " + firstUniqChar("aabb")); // Expected: -1
        
        // Test case 4: Single character
        // Input: "a" -> Output: 0 (only one char)
        System.out.println("Test 4: " + firstUniqChar("a")); // Expected: 0
        
        // Test case 5: Empty string
        // Input: "" -> Output: -1 (no chars)
        System.out.println("Test 5: " + firstUniqChar("")); // Expected: -1
        
        // Test case 6: First unique at end
        // Input: "abccba" -> Output: -1 (no unique chars)
        System.out.println("Test 6: " + firstUniqChar("abccba")); // Expected: -1
        
        // Test case 7: First unique in middle
        // Input: "abcabcde" -> Output: 6 (first 'd' at index 6)
        System.out.println("Test 7: " + firstUniqChar("abcabcde")); // Expected: 6
        
        // Test case 8: Large string with unique char at beginning
        // Input: "abcdefghijklmnopqrstuvwxyz" -> Output: 0 (first 'a')
        System.out.println("Test 8: " + firstUniqChar("abcdefghijklmnopqrstuvwxyz")); // Expected: 0
    }
}

Representative Test Cases:

1. Basic case: "leetcode" → Expected: 0 (index of first unique character 'l')
2. All unique: "abcdef" → Expected: 0 (first character is unique)
3. No unique: "aabb" → Expected: -1 (no unique characters)
4. Single character: "a" → Expected: 0 (only one character)
5. Empty string: "" → Expected: -1 (no characters to process)
6. Unique at end: "abccba" → Expected: -1 (all characters repeated)
7. Unique in middle: "abcabcde" → Expected: 6 (character 'd' at index 6)
8. Large unique: "abcdefghijklmnopqrstuvwxyz" → Expected: 0 (first character unique)

Tricky Case:

• Input: "aab" → Expected: 2 (character 'b' at index 2 is unique, but first occurrence of 'a' is at index 0)

Boundary Case:

• Input: "" (empty string) → Expected: -1 (edge case handling for empty input)

The test cases cover all major scenarios including edge cases, ensuring robust validation of the solution's correctness across various input conditions.

11. Final Summary

The core insight is to leverage the fixed alphabet size (26 lowercase letters) to achieve linear time complexity by making two passes through the string: first to count character frequencies, then to find the first character with a count of one. This approach is optimal because it processes each character exactly twice and uses constant extra space, making it both time and space efficient for the given constraints. The solution elegantly handles all edge cases including empty strings, single characters, and strings with no unique characters.