First unique character in a string

2.1K

You are given a string with some repeating characters and some unique characters. Find the first unique character and return its index.

Example 1:
Input: studyAlgorithms
Output: 2

Example 2:
Input: iLoveToCode
Output: 0

Problem Statement:

I want to simplify the problem statement first before we begin to solve it. An input string consists of some uppercase and lowercase characters which may or may not be repeated. Out of all the unique characters, you need to return the characters that occurs first in the string. In the first example studyAlgorithms, s, and t are repeated later in the string. The first unique character that you can find hence would be u. It’s index is 2 and hence that would be the answer. Similarly, in the second example iLoveToCode, we have i, l, v, t, c, d as the unique characters, but the first one to appear is i. It appears at index 0 and hence the answer. An opposite problem would be to find the duplicate characters in a string.

Brute Force Method:

First, we would try to solve this problem with the most naive method possible. It is very clear that we need to go through the entire string to determine if a character is unique or not. The brute force algorithm to solve this problem would be:

• Pick a character in the string
• Start with the first character and traverse all the way to the to see if the character occurs anywhere else.
• If yes, then this is not your answer, move to the second character and repeat the process.
• If no, then this is the first unique character and hence your answer.

Optimized Approach:

The above approach takes up a time complexity of O(n^2) which is not the characteristic of a good programmer. We want our programs to run fast and avoid unnecessary computations. Ask yourself the question, do we really need to scan the entire string over and over again? If we can just do some kind of pre-processing in the first scan, then we can reduce the time taken the subsequent checks.

1. Create an empty map, that would store the character and its frequency.
2. Start scanning the string from the first character. If the character does not exist in the map, add it and update the frequency to 1.
3. If it already exists, increment the frequency by 1.
4. Once this map is complete, do a second scan of the string one character at a time.
5. Check the frequency of each character in the hashmap.
6. If the frequency of a character is 1, this is the first unique character in the string.

Code:

  public int firstUniqueChar(String str) {

    int index = -1;

    Map<Character, Integer> charFreqMap = new HashMap<>();

    // Update the map
    for (int i = 0; i < str.length(); i++) {
      char c = str.charAt(i);

      // Get the current frequency
      int freq = charFreqMap.getOrDefault(c, 0);

      // Update the map
      charFreqMap.put(c, (freq + 1));
    }

    for (int i = 0; i < str.length(); i++) {
      if (charFreqMap.get(str.charAt(i)) == 1) {
        index = i;
        break;
      }
    }

    return index;
  }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(1) since the maximum characters that we can get is 26.

You can find a working solution here.
The code and test cases can also be found on Github.
A similar problem can be found on Leetcode.

Video Explanation: