First Unique Character In A String – 387. LeetCode

The “First Unique Character in a String” problem asks you to find the index of the first character in a string that appears only one. If no such character exists, return -1. This problem is about efficiently identifying a character that is unique while processing all the characters in the string.

Brute Force Approach

public int firstUniqChar(String s) {
    for (int i = 0; i < s.length(); i++) {
        boolean isUnique = true;
        for (int j = 0; j < s.length(); j++) {
            if (i != j && s.charAt(i) == s.charAt(j)) {
                isUnique = false;
                break;
            }
        }
        if (isUnique) {
            return i;
        }
    }
    return -1;
}

• The outer loop goes through each character in the string
• The inner loop checks if the current character matches any other character in the string.
• If the character does not match, return its index.
• If no unique character is found, return -1.

Optimized Approach

To optimize, use a HashMap to count character frequencies. This reduces the time complexity by avoiding redundant comparisons.

A HashMap allows for:

1. Efficient counting: We can count the frequency of each character in O(n) time.

2. Fast lookups: Hash maps have average O(1) lookup time, which makes checking frequencies efficient.

Algorithm and Data Structure

1. Pattern: Use a counting pattern with a hash map to track character frequencies.
2. When to Use:
   • Use this approach when:
     • You need to quickly access and update counts of elements
     • You are searching for elements based on their frequency or uniqueness.
3. Why This Strategy?
   • The hash map eliminates the need for repeated comparisons, making the algorithm linear in time complexity.
   • This fits the broader frequency counting pattern, often used in problems like finding duplicates, grouping elements, or determining uniqueness.

Algorithm Steps

1. Count Frequencies:
   • Iterate through the string and record the frequency of each character in a hash map.
2. Find First Unique Character:
   • iterate through the string again and check the hash map for a character with a frequency of 1
3. Return the Index:
   • Return the index of the first unique character or -1 if none exists.

Optimized Code

import java.util.HashMap;

public class Solution {
    public int firstUniqChar(String s) {
        // Step 1: Create a HashMap to store character frequencies
        HashMap<Character, Integer> charFrequency = new HashMap<>();

        // Step 2: Count frequencies of each character
        for (char c : s.toCharArray()) {
            charFrequency.put(c, charFrequency.getOrDefault(c, 0) + 1);
        }

        // Step 3: Find the first unique character
        for (int i = 0; i < s.length(); i++) {
            if (charFrequency.get(s.charAt(i)) == 1) {
                return i; // Return the index of the first unique character
            }
        }

        // Step 4: If no unique character is found, return -1
        return -1;
    }
}

Line-By-Line Breakdown

1. HashMap Initialization

HashMap<Character, Integer> charFrequency = new HashMap<>();

• Creates a hash map to count the frequency of each character
• Why: Efficiently store and access character counts

2. Count Frequencies

for (char c : s.toCharArray()) {
    charFrequency.put(c, charFrequency.getOrDefault(c, 0) + 1);
}

• Converts the string into a character array and iterates through it.
• Uses getOrDefault to update the count of each character.

3. Find First Unique Character

for (int i = 0; i < s.length(); i++) {
    if (charFrequency.get(s.charAt(i)) == 1) {
        return i;
    }
}

• Iterates through the string again.
• Checks the frequency of each character in the hash map.
• Returns the index of the first character with a frequency of 1.

Key Takeaways

1. The brute force approach is straightforward but inefficient.

2. Using a hash map for frequency counting improves both time and space complexity.

3. The frequency counting pattern with a hash map is a versatile tool for problems involving uniqueness or duplicates.

This optimized solution is fast, memory-efficient, and leverages common algorithmic patterns effectively!