Solution


Approach 1: Linear time solution

The best possible solution here could be of a linear time because to ensure that the character is unique you have to check the whole string anyway.

The idea is to go through the string and save in a hash map 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 hash map 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.

!?!../Documents/387_LIS.json:1000,621!?!

Complexity Analysis

  • Time complexity : since we go through the string of length N two times.
  • Space complexity : since we have to keep a hash map with N elements.

Analysis written by @liaison and @andvary