LeetCode in Ruby: 387. First Unique Character in a String Kaitian Xie twitter logo github logo Mar 19・1 min read

LeetCode in Ruby (11 Part Series)

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)

LeetCode in Ruby (11 Part Series)

DISCUSS
Classic DEV Post from Jan 3

Conversation with an Author - Ali Spittel

dev.to is where software developers stay in the loop and avoid career stagnation.  