loading...
Cover image for Top Interview Question: Finding the First Unique Character in a String using Linear Time

Top Interview Question: Finding the First Unique Character in a String using Linear Time

alisabaj profile image Alisa Bajramovic Updated on ・4 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Today's algorithm is the First Unique Character in a String problem:

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

For example, if you were given the string "APPLESAUCE", the first unique character is "L" at index 3, since "L" is only found once in the string, and it comes before any other unique characters.

This problem is listed on Leetcode's Top Classic Interview Questions list. Like most questions that are frequently found in technical interviews, this one can be solved in a number of different ways. Today, I'll solve it in JavaScript using a hash. Hashes are very useful data structures when solving algorithms because looking up and storing variables in a hash takes up little space (O(n)), and is done in a short amount of time (O(1) on average). (If you're interested in Big O complexity, you should check out this cheat sheet.)

In this post, I'll discuss my approach to this problem, and then will code the solution. This approach will end up taking linear time (O(n)).

Approaching the Problem

A hash is useful for problems that ask you to find unique values because you can quickly store elements and their frequency. In this algorithm, we want to take a string, and count how many times each character in the string appears. We can do this by creating an empty hash and then iterating through the string, checking if each letter is already a key in the hash. If the letter is already in the hash, we'll increment its value, since we found the same letter another time. If the letter is not already a key in the hash, that means we haven't yet seen it in the string, so we'll set its value in the hash equal to 1.

To see this method on a smaller scale, let's say you're given that string = ABA, and you want to create a hash that stores how many times each letter is found in the string. We'd start by creating an empty hash, called letterHash. We'd then want to use a for loop to go through each element in the string, and check to see if it's already in the hash. If it is in the hash, we can increment its value. If it's not in the hash, we'll initialize the letter as a key in the hash, and set its value equal to 1.

// initialize an empty hash
let letterHash = {};
// use a for loop to check each letter in the string
for (let i = 0; i < string.length; i++) {
  // if that letter is already found in the hash...
  if (string[i] in letterHash) {
    // ...then increment its value by 1
    letterHash[string[i]]++;
  } else {
    // otherwise, initialize it in the hash, setting its value equal to 1
    letterHash[string[i]] = 1;
  }
}

This would give us the result of letterHash = {"A": 2, "B": 1}.

Now, we want to check which is the first unique element in the string. There's a few ways to go about this, but one would be to go through the hash a second time. At each letter, check the hash to see what the value for that letter is. The value indicates how many times that letter has been seen in the string. If the value is 1, then we know it's unique, so we can return that index. We know that we're returning the first unique index because we're using a for loop, going from the start to the end of the string, which means we'll find the first unique character first.

Coding the Solution

We'll start by initializing an empty hash, and setting up the first for loop.

function firstUniqChar(s) {
    let hash = {};
    for (let i = 0; i < s.length; i++) {
        //...
    }
    //...
}

In the for loop, we'll check each letter of s to see if it's in hash. We can access each letter with s[i], since i is the index. If the letter is in hash, we'll want to increment its value, since we found a letter multiple times. If it's not in hash, we'll initialize the value, setting it equal to 1.

function firstUniqChar(s) {
    let hash = {};
    for (let i = 0; i < s.length; i++) {
        if (s[i] in hash) {
            hash[s[i]]++;
        } else {
            hash[s[i]] = 1;
        }
    }
    //...
}

We now have a hash whose keys are each letter in the string, and values are the number of times those letters are found in the string. Next, we'll want to set up a second for loop, going through the string again. In this for loop, we'll want to see what the value is for that letter in hash. If the value of that letter is 1, then we know it was only found once in the string, so we can return its index, i.

function firstUniqChar(s) {
    let hash = {};
    for (let i = 0; i < s.length; i++) {
        if (s[i] in hash) {
            hash[s[i]]++;
        } else {
            hash[s[i]] = 1;
        }
    }
    for (let i = 0; i < s.length; i++) {
        if (hash[s[i]] === 1) {
            return i;
        }
    }
    //...
}

If there were no instances of a letter having a value of 1 in the hash, that means there are no unique characters in the string. As per the instructions, if that's the case, then we should return -1.

function firstUniqChar(s) {
    let hash = {};
    for (let i = 0; i < s.length; i++) {
        if (s[i] in hash) {
            hash[s[i]]++;
        } else {
            hash[s[i]] = 1;
        }
    }
    for (let i = 0; i < s.length; i++) {
        if (hash[s[i]] === 1) {
            return i;
        }
    }
    return -1;
}

Even though we went through the string two times, the time complexity is still O(n) (rather than O(2n) or O(n2)). It's not O(2n) because coefficients (in this case, the 2) are removed in Big O notation for simplicity. It's not O(n2) because the for loops are not nested--we go through the string two separate times, not at the same time.

Let me know in the comments if you have questions or alternate solutions to this problem!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide
 

leetcode.com/problems/elimination-...

Hi Alisa,
Can you please explain the above problem and its solution in one of your posts soon?
Thank you :)

 

I personally faced this problem in my last job's code interview, I half solved it as I was very nervous, but I got the job nonetheless, now It all makes sense to me, thanks for sharing :)