LeetCode in Ruby: 387. First Unique Character in a String

Index and RIndex

def first_uniq_char(s)
  s.each_char.with_index do |char, i|
    if s.index(char) == s.rindex(char)
      return i
    end
  end

  return -1
end

The String#index returns the index of the first occurrence and String#rindex returns the index of the last occurrence. If both of them return the same index while iterating through s, it’s the first unique character.

Time complexity: O(n)

Extra memory: O(1)

Hash

def first_uniq_char(s)
  return -1 if s.length == 0

  counts = Hash.new 0
  s.each_char do |char|
    counts[char] += 1
  end

  s.each_char.with_index do |char, i|
    if counts[char] == 1
      return i
    end
  end

  return -1
end

First of all, we create a Hash called counts that stores the counts of each character in s Then we iterate through s to see if there is a character with count of exactly 1. If so, return its index, otherwise return -1 instead.

Time complexity: O(n)

Extra memory: O(n)

Two Arrays

def first_uniq_char(s)
  counts = Array.new(26, 0)
  positions = Array.new(26, nil)
  offset = 'a'.ord

  (0...s.length).each do |index|
    char = s[index]
    pos = char.ord - offset
    counts[pos] +=1
    positions[pos] = index if positions[pos].nil?
  end

  s.each_char do |char|
    pos = char.ord - offset
    if counts[pos] == 1
      return positions[pos]
    end
  end

  return -1
end

This is very similar to the previous approach. Basically, we use two arrays to simulate the hash named counts in the Hash approach.

Time complexity: O(n)

Extra memory: O(n)