Scale Engineer

First Unique Character in a String

Easy
#0374Time: 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.10 companies
Patterns
Counting
Data structures
Hash TableStringQueue
Companies
EPAM SystemsGoldman SachsOzonPayPal

Prompt

[Fetch error]

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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).

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem