LeetCode 387. First Unique Character in a String

Description

https://leetcode.com/problems/first-unique-character-in-a-string/description/

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

Note: You may assume the string contain only lowercase letters.

Explanation

We introduce an array with a length of 26 to save the number of times each character appears in the string.

The idea is to go through the string and save the number of times each character appears in the string. That would take  time, where N is a number of characters in the string.  

And then we go through the string the second time, this time we use the array as a reference to check if a character is unique or not. If the character is unique, one could just return its index. The complexity of the second iteration is  as well.

Video Tutorial

Java Solution

Complexity Analysis

  • Time complexity:  since we go through the string of length N two times.
  • Space complexity: since we use an array with 26 elements.

Leave a Reply

Your email address will not be published. Required fields are marked *