This is the 14th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

preface

Stack and queue are good brothers in data structures and algorithms. Stack mechanism is last in, first out, can be understood as a cup, the later put in the cup must be taken out first. The mechanism of queue is first in, first out, which can be understood as a queue, and the first person in line will be the first to receive. Stack and queue have a wide range of applications in programming, its syntax is not described here, the reader can refer to the relevant information if interested. Here’s how to use the idea of queues to solve a LeetCode problem.

The title

Given a string, find its first non-repeating character and return its index. If none exists, -1 is returned.

Example:

s = "leetcode"return0

s = "loveleetcode"return2
Copy the code

Tip: You can assume that the string contains only lowercase letters.

thinking

For this problem, the first thing you can think of is iterating through the string, and for each character of the string, iterating again to see if there are duplicate characters. This will solve our problem, but the time complexity of the solution is O(n^2), which is obviously not elegant!

So how can we improve our algorithm? There are many answers, and one of them is the idea of queues.

First, we define a hash table to store the index corresponding to the character, and if the character occurs a second time, we define the index -1. Then, you define a queue (array in this case) that stores all the characters that meet the criteria and their corresponding indexes while iterating through the string. At the end of the loop, the first element of the queue is the character with the smallest index that meets the condition. That would solve our problem.

Here’s the code.

answer

The queue

var firstUniqChar = function(s) {
  const position = new Map(a)/ / a hash table
  const q = [] / / the queue
  for (let [i, ch] of Array.from(s).entries()) {
    if(! position.has(ch)) { position.set(ch, i)// set the value of character CH to index I
      q.push([s[i], i]) // put [character, index] in queue
    } else {
      position.set(ch, -1) // Set the value of ch in the hash table to -1
      while (q.length && position.get(q[0] [0= = = -])1) { // Delayed deletion, which removes the unsatisfied elements from the queue
        q.shift() // Remove the first element of the array: equivalent to the fifO of the queue}}}return q.length ? q[0] [1] : -1
}
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the length of string S.

  • Space complexity: O (| Σ |), in the subject s only contain lowercase letters, so | Σ | 26 or less.

Delayed deletion: Even if a character appears more than once in a queue, as long as it is not at the head of the queue, it does not affect the answer and we do not need to delete it.

reference

  • 387. The first unique character in a string