First Unique Character in a String

EASY

Description

[Fetch error]

Approaches

Checkout 3 different approaches to solve First Unique Character in a String. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Nested Loops

This is the most straightforward but least efficient approach. It involves iterating through each character of the string and, for each character, iterating through the string again to see if any other character matches it. If no match is found after checking the entire string, we've found our first unique character.

Algorithm

Iterate through the string with an outer loop from i = 0 to n-1, where n is the length of the string.
For each character s[i], assume it is unique.
Start an inner loop from j = 0 to n-1 to check for duplicates.
If a character s[j] is found such that s[i] == s[j] and i != j, then the character s[i] is not unique. Break the inner loop.
If the inner loop completes without finding any duplicates, it means s[i] is the first unique character. Return its index i.
If the outer loop completes and no unique character is found, return -1.

The brute-force method uses two nested loops. The outer loop picks a character, and the inner loop checks if that character appears anywhere else in the string. A boolean flag, isUnique, can be used to track whether a duplicate has been found for the character selected by the outer loop. If the inner loop finishes and the flag remains true, we have found the first unique character and can return its index. If the outer loop finishes without finding any such character, it means no unique characters exist, and we return -1.

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

Complexity Analysis

Time Complexity: O(N^2), where N is the length of the string. For each of the N characters, we iterate through the string again, which takes O(N) time.Space Complexity: O(1), as no extra data structures are used that scale with the input size.

Pros and Cons

Pros:

Simple to understand and implement.
Uses constant extra space, O(1).

Cons:

Highly inefficient with a time complexity of O(N^2).
Will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for larger inputs (e.g., N > 10^4).

Code Solutions

Checking out 4 solutions in different languages for First Unique Character in a String. Click on different languages to view the code.

class Solution {
public
  int firstUniqChar(String s) {
    int[] cnt = new int[26];
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      ++cnt[s.charAt(i) - 'a'];
    }
    for (int i = 0; i < n; ++i) {
      if (cnt[s.charAt(i) - 'a'] == 1) {
        return i;
      }
    }
    return -1;
  }
}

Video Solution

Watch the video walkthrough for First Unique Character in a String

Patterns:

Counting

Data Structures:

Hash TableStringQueue

Companies:

EPAM Systems |Goldman Sachs |Ozon |PayPal |