First Unique Character in a String

Problem Statement

The objective of this task is to process a given string s and find the first character that does not repeat anywhere else in the string. Once identified, the index of this non-repeating character is to be returned. If every character within the string repeats, the function should return -1. This problem tests efficient string processing with attention to time and space constraints.

Examples

Example 1

Input:

s = "sampletext"

Output:

0

Explanation:

The character 's' at index 0 is the first character that does not occur at any other index.

Example 2

Input:

s = "lovecodehere"

Output:

2

Explanation:

The character 'v' at index 2 does not repeat in the string.

Example 3

Input:

s = "aabb"

Output:

-1

Explanation:

All characters repeat, so there is no non-repeating character.

Constraints

• 1 <= s.length <= 10^5
• s consists of only lowercase English letters.

Approach and Intuition

To solve this efficiently:

1. Build a frequency map:

   • Traverse the string once and count the frequency of each character using a fixed-size array (length 26, for lowercase letters).

2. Scan for the first unique character:

   • Traverse the string a second time.
   • Return the index of the first character with a count of 1 in the frequency array.

3. Edge Case:

   • If no such character exists, return -1.

Example Walkthroughs:

• For s = "sampletext":

  • Frequency map: {'s': 1, 'a': 1, 'm': 1, 'p': 1, 'l': 1, 'e': 3, 't': 2, 'x': 1}
  • The first unique character is 's' at index 0.

• For s = "lovecodehere":

  • Frequency map: {'l': 1, 'o': 2, 'v': 1, 'e': 4, 'c': 1, 'd': 1, 'h': 1, 'r': 1}
  • The first non-repeating character is 'v' at index 2.

• For s = "aabb":

  • Frequency map: {'a': 2, 'b': 2}
  • No character appears only once → return -1.

Efficiency:

• Time complexity: O(n), where n is the length of the string.
• Space complexity: O(1), due to fixed-size frequency array (26 letters).
• The constraints allow up to 100,000 characters, so avoiding nested loops ensures optimal performance.

Solutions

class Solution {
    public int firstUniqueCharacter(String str) {
        HashMap<Character, Integer> charFrequency = new HashMap<>();
        int length = str.length();
        // Populate character frequency map
        for (int i = 0; i < length; i++) {
            char ch = str.charAt(i);
            charFrequency.put(ch, charFrequency.getOrDefault(ch, 0) + 1);
        }
        
        // Search for the first unique character
        for (int i = 0; i < length; i++) {
            if (charFrequency.get(str.charAt(i)) == 1)
                return i;
        }
        return -1;
    }
}