First Unique Character in a String - Leetcode 387 | First Non-Repeating Character in a String

Finding the first non-repeating character in a string is a common problem in coding interviews and competitive programming. It's listed as Leetcode Problem 387: First Unique Character in a String. In this article, we’ll walk through a clean and efficient solution, discussing its approach, key concepts, and an optimized implementation in Java.

Problem Description

You are given a string s. The task is to return the index of the first non-repeating character in the string. If there is no such character, return -1.

Example 1:

Input: "leetcode"

Output: 0

Explanation: The first non-repeating character is 'l' and appears at index 0.

Example 2:

Input: "loveleetcode"

Output: 2

Explanation: The first non-repeating character is 'v' and appears at index 2.

Approach: Using Hash Maps

The best way to solve this problem efficiently is to use a hash map (or a LinkedHashMap in Java) to store the count of each character while preserving the order of characters as they appear in the string. This allows us to:

Traverse the string once to count the frequency of each character.
Traverse the map to find the first character with a frequency of 1.

This two-step process ensures we solve the problem in linear time—O(n)—which is efficient enough for large inputs.

Java Code Implementation

private static char getFirstNonRepeatingCharacter(String str) {
	    if (str == null || str.isEmpty()) return '-'; 
                            // Returning special char for no result
	    
	    Map<Character, Integer> map = new LinkedHashMap<>();
	    
	    // Counting occurrences of each character
	    for (char c : str.toCharArray()) {
	        map.put(c, map.getOrDefault(c, 0) + 1);
	    }
	    
	    // Find the first character with count 1
	    for (Map.Entry<Character, Integer> entry : map.entrySet()) {
	        if (entry.getValue() == 1) {
	            return entry.getKey();
	        }
	    }
	    
	    return '-'; // Returning special char if no unique character is found
	}

Explanation of the Code

Edge Case Handling: We first check if the input string is null or empty. If so, we return '-' to indicate that no unique character exists.
Using LinkedHashMap: We choose a LinkedHashMap because it preserves the order of insertion, which is crucial for finding the first unique character. This map stores each character as the key and its occurrence count as the value.
Counting Character Frequencies: We loop through the string using toCharArray(), which converts the string into a character array. For each character, we update its count in the map.
Finding the First Non-Repeating Character: After building the frequency map, we iterate through the map’s entries to find the first character with a count of 1. If found, we return that character.
Return '-': If no non-repeating character exists, the function returns '-'.

Time Complexity

The time complexity of this solution is O(n) where n is the length of the input string. This is because:

We traverse the string once to build the frequency map.
We traverse the map (which contains at most n entries) to find the first unique character.

Edge Cases to Consider

Empty String: The function should return a special character (e.g., '-') when the input string is empty.
All Characters Repeat: In cases like "aabbcc", there are no non-repeating characters, so the function returns '-'.
Only One Character: For a string like "a", the function will return 'a' because it is the only character and hence non-repeating.

Common Mistakes

Ignoring Edge Cases: Ensure that your solution handles special cases like empty strings and strings with no unique characters.
Using Regular HashMap: A regular HashMap doesn’t maintain insertion order, which would make it impossible to find the first non-repeating character efficiently. Always use LinkedHashMap or other ordered collections.
Incorrect Return Value: Ensure the function returns an appropriate value ('-' in this case) when no unique character is found.

Conclusion

By leveraging a LinkedHashMap, we can efficiently find the first non-repeating character in a string in O(n) time. This method is both simple and scalable, making it ideal for handling larger strings during coding interviews or competitive programming challenges.

This approach guarantees that we check each character only once, making it both space-efficient and time-efficient. Feel free to try it out and modify the solution to suit your coding style or language of choice!

#First non-repeating character, #Leetcode 387, #Java solution, #hash map, #LinkedHashMap, #coding interview, #time complexity, #data structures