First Non-Repeating Character

First Non-Repeating Character in a String: A Complete Guide with Java Solution

by

Introduction

Finding the first non-repeating character in a string is a popular coding challenge, often appearing in technical interviews at top companies such as Amazon, Microsoft, and Goldman Sachs. This problem evaluates your understanding of data structures, particularly hashing, and your ability to optimize algorithms.

Why is This Problem Important?

This problem is frequently asked in interviews because it tests several core programming skills:

  • Hashing Concepts: Demonstrates the use of hash tables for efficient lookups.
  • String Manipulation: Highlights proficiency in handling and processing strings.
  • Optimization: Challenges you to design a solution with linear time complexity.

Problem Statement

Given: A string s consisting of lowercase Latin letters.
Task: Return the first non-repeating character in the string. If all characters repeat, return '$'.

Example

InputOutputExplanation
"geeksforgeeks"'f''f' is the first character that does not repeat.
"racecar"'e''e' is the only non-repeating character.
"aabbccc"'$'All characters in the string repeat.

Optimized Approach

Key Concepts

  1. Hashing: Use a hash table (e.g., Map) to count the frequency of each character.
  2. Order Maintenance: Utilize a LinkedHashMap to preserve the order of insertion.
  3. Efficiency: Achieve a solution with a single pass through the string and constant space for storage.

Time Complexity

  • Building the frequency map: O(n)O(n)O(n), where N is the length of the string.
  • Finding the first unique character: O(n)O(n)O(n).
  • Overall Complexity: O(n)O(n)O(n).

Space Complexity

  • Auxiliary Space: O(1)O(1)O(1), as we only store a constant number of Latin characters (26 lowercase letters).

Java Code for First Non-Repeating Character

import java.util.*;

public class FirstNonRepeatingCharacter {

    public static char firstNonRepeatingCharacter(String s) {
        // Step 1: Create a frequency map to count occurrences of each character
        Map<Character, Integer> frequencyMap = new LinkedHashMap<>();

        // Step 2: Populate the frequency map
        for (char c : s.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        // Step 3: Iterate through the map to find the first character with frequency 1
        for (char c : frequencyMap.keySet()) {
            if (frequencyMap.get(c) == 1) {
                return c;
            }
        }

        // Step 4: If no non-repeating character is found, return '$'
        return '$';
    }

    public static void main(String[] args) {
        // Test cases
        System.out.println(firstNonRepeatingCharacter("geeksforgeeks")); // Output: 'f'
        System.out.println(firstNonRepeatingCharacter("racecar"));       // Output: 'e'
        System.out.println(firstNonRepeatingCharacter("aabbccc"));       // Output: '$'
    }
}

Explanation of the Solution

Hash Table for Frequency Count

  • A LinkedHashMap is used to store characters as keys and their counts as values.
  • Characters are added in the order of their appearance.

First Unique Character

  • Iterate through the keys of the map.
  • The first character with a count of 1 is returned as the answer.

Edge Cases

  • Empty String: Returns '$'.
  • No Unique Characters: Returns '$'.

Common Edge Cases

InputOutputExplanation
"abcdef"'a'All characters are unique; 'a' is the first.
"aabbcc"'$'No unique character exists in the string.
""'$'The string is empty, so no character is found.
"aabbccd"'d''d' is the first non-repeating character.

Where This Problem Was Asked

This question has been asked in technical interviews for roles involving data structures and algorithms at companies such as:

  • Amazon
  • Microsoft
  • Flipkart
  • Goldman Sachs
  • Ola Cabs
  • PayU

Find the Second Largest Element in an Array

FAQs About First Non-Repeating Character

1. What is the Time Complexity of This Approach?

The approach has a time complexity of O(n)O(n)O(n), where N is the length of the string.

2. Why Use LinkedHashMap?

A LinkedHashMap maintains the insertion order, making finding the first non-repeating character easier.

3. What If the String Contains Uppercase Letters?

The solution can be extended to support uppercase letters by considering all 52 alphabetic characters.

4. Can This Problem Be Solved Without Hashing?

Yes, by iterating through the string twice: once to count frequencies and once to find the unique character. However, hashing is more efficient.

Real-Life Applications

  • Natural Language Processing: Identifying unique letters or words in text.
  • Data Parsing: Processing input for unique values.
  • Compression Algorithms: Tracking frequency for data compression.

Conclusion

Finding the first non-repeating character in a string is a crucial problem that reinforces hashing, optimization, and string manipulation concepts. By understanding and applying the steps outlined above, you’ll be well-prepared to tackle similar challenges in coding interviews.

Learn more about this problem on GeeksforGeeks

Leave a Comment