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)
Top comments (0)