# First Unique Character in a String
**Difficulty:** EASY
[External](https://leetcode.com/problems/first-unique-character-in-a-string)
Canonical: https://scaleengineer.com/dsa/problems/first-unique-character-in-a-string
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String, Queue
**Companies:** [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Ozon](https://scaleengineer.com/companies/ozon), [PayPal](https://scaleengineer.com/companies/paypal), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
\[Fetch error\]

# Approaches
## 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.
**Time:** 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:** O(1), as no extra data structures are used that scale with the input size.
**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).
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Using String Search Methods
This approach leverages built-in string searching functions. A character is unique if and only if its first index in the string is the same as its last index. We can iterate through the 26 lowercase English letters, and for each letter, we find its first and last index in the input string. If they are the same, the character is unique. We keep track of the minimum index found among all unique characters.
**Time:** O(N). The outer loop runs a constant number of times (26). Inside the loop, `indexOf` and `lastIndexOf` each take O(N) time in the worst case. Thus, the total complexity is O(26 * N), which simplifies to O(N). · **Space:** O(1), as we only use a few variables to store the indices, regardless of the input string size.
**Pros:** Linear time complexity O(N).; Constant space complexity O(1).; Code is often concise and easy to read.
**Cons:** Although the asymptotic complexity is O(N), it can be slower in practice than the hash map approach because it may perform many passes over the string (up to 52 scans for `indexOf` and `lastIndexOf`).
### Explanation
Instead of iterating through the string itself, we iterate through the constant-size alphabet ('a' through 'z'). For each character, we use `s.indexOf(char)` and `s.lastIndexOf(char)`. If these two methods return the same index, it confirms the character appears exactly once. We want the *first* such unique character, so we maintain a variable, `minIndex`, to store the minimum index seen so far among all unique characters. This ensures we find the one that appears earliest in the string.

```java
class Solution {
    public int firstUniqChar(String s) {
        int minIndex = Integer.MAX_VALUE;
        for (char c = 'a'; c <= 'z'; c++) {
            int index = s.indexOf(c);
            // Check if character exists and is unique
            if (index != -1 && index == s.lastIndexOf(c)) {
                minIndex = Math.min(minIndex, index);
            }
        }
        
        // If minIndex was never updated, no unique character was found
        return minIndex == Integer.MAX_VALUE ? -1 : minIndex;
    }
}
```
### Algorithm
- Initialize a variable `minIndex` to a very large value (or -1 as a flag).
- Iterate through all possible characters in the alphabet (from 'a' to 'z').
- For each character `c`, find its first occurrence in the string using `s.indexOf(c)`.
- If the character `c` exists in the string (i.e., `indexOf` does not return -1), check if its last occurrence is at the same position using `s.lastIndexOf(c)`.
- If `s.indexOf(c) == s.lastIndexOf(c)`, the character is unique. We then update `minIndex` with the smaller value between the current `minIndex` and this character's index.
- After checking all 26 characters, if `minIndex` is still the initial large value, it means no unique character was found, so return -1. Otherwise, return `minIndex`.

## Two-Pass approach with Frequency Counting
This is the most common and efficient approach. It solves the problem in two linear passes. The first pass is to build a frequency count of all characters in the string. The second pass is to iterate through the string again and return the index of the first character that has a frequency of 1.
**Time:** O(N), where N is the length of the string. We make two passes through the string, one to count frequencies (O(N)) and one to find the unique character (O(N)). The total time is O(N) + O(N) = O(N). · **Space:** O(1), because the size of the frequency array (26) is constant and does not depend on the length of the input string.
**Pros:** Optimal time complexity of O(N).; Generally faster in practice than the `indexOf` method due to better data locality and fewer total operations.; A standard and widely applicable pattern for frequency-related problems.
**Cons:** Requires two separate passes over the input string.; Uses extra space for the frequency map, although it's constant space (O(1)) for a fixed alphabet.
### Explanation
We can use a data structure to store the counts of each character. Since the problem states the string only contains lowercase English letters, a simple integer array of size 26 is a highly efficient choice for a frequency map. `counts[c - 'a']` will store the frequency of character `c`.

First, we iterate through the string to populate this `counts` array. Then, we iterate through the string a second time. For each character, we check its count in the array. The first time we find a character whose count is 1, we've found our answer and can immediately return its index. If we finish the second loop, it means no character had a count of 1, so we return -1.

```java
class Solution {
    public int firstUniqChar(String s) {
        int[] counts = new int[26];
        int n = s.length();

        // First pass: build frequency map
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            counts[c - 'a']++;
        }

        // Second pass: find first unique character
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (counts[c - 'a'] == 1) {
                return i;
            }
        }

        return -1;
    }
}
```
### Algorithm
- **First Pass (Frequency Counting):** Create a frequency map (or an integer array of size 26 for lowercase letters). Iterate through the input string `s` from beginning to end. For each character, increment its corresponding count in the frequency map.
- **Second Pass (Find First Unique):** Iterate through the string `s` a second time, again from beginning to end.
- For each character `s[i]`, look up its count in the frequency map.
- If the count is 1, this is the first unique character we've encountered. Return its index `i`.
- If the second loop completes without finding any character with a frequency of 1, it means no unique characters exist. Return -1.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @return {number} */ var firstUniqChar = function (s) {
  const cnt = new Array(26).fill(0);
  for (const c of s) {
    ++cnt[c.charCodeAt() - " a ".charCodeAt()];
  }
  for (let i = 0; i < s.length; ++i) {
    if (cnt[s[i].charCodeAt() - " a ".charCodeAt()] === 1) {
      return i;
    }
  }
  return -1;
};

```

### CPP

```cpp
class Solution {
public:
  int firstUniqChar(string s) {
    int cnt[26]{};
    for (char &c : s) {
      ++cnt[c - 'a'];
    }
    int n = s.size();
    for (int i = 0; i < n; ++i) {
      if (cnt[s[i] - 'a'] == 1) {
        return i;
      }
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    def firstUniqChar(self, s: str) -> int: cnt = Counter(s) for i, c in enumerate(s): if cnt[c] == 1: return i return - 1

```