First Unique Character in a String (Ruby)

Today we solve a very popular 'kata' on Leetcode #387 First Unique Character in a String

Difficulty level: Easy

Related Topics: Hash Table, String

Disclaimer: You might have different results in Runtime and Memory Usage, it's okay 🤣 it how it works.

---

Description:

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

Examples:

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

Note:

 You may assume the string contains only lowercase English letters.

And your playground looks like this:

def first_uniq_char(s)
end

---

Solution 1

We know that we can get an empty string. Let's first check it, then start to search for unique characters.

If string has no length, that means it's empty and we return -1

    if(!s.empty?) then

    ...

    else
        return -1
    end

Then we declare an empty hash

hash_table = {}

And count how many times a character appears.

If we have a character in the dictionary we increase its value by one, if not the value will be equal to one.

s.split("").each do |char|
    if hash_table.has_key?(char) then
    hash_table[char] = hash_table[char] + 1
    else
    hash_table[char] = 1
    end
end

Then we go thru the dictionary and return the first character which has value 1

s.split("").each_with_index do |char, i|
    if hash_table[char] == 1 then
        return i
    end
end

Full solution

def first_uniq_char(s)
  if(!s.empty?) then
    hash_table = {}

    s.split("").each do |char|
      if hash_table.has_key?(char) then
        hash_table[char] = hash_table[char] + 1
      else
        hash_table[char] = 1
      end
    end

    s.split("").each_with_index do |char, i|
        if hash_table[char] == 1 then
            return i
        end
    end

    return -1

  else
    return -1
  end
end

---

Let's submit it and see the result.

Runtime: 1060 ms, faster than 5.49% of Ruby online submissions for First Unique Character in a String.
Memory Usage: 15.9 MB, less than 10.00% of Ruby online submissions for First Unique Character in a String.

I don't really like this result 🥵 let's improve it!

---

Solution 1.1

We split string two times, let's move it a variable

slided_string = s.split("")

Full solution

def first_uniq_char(s)
  if(!s.empty?) then
    hash_table = {}
    slided_string = s.split("")

    slided_string.each do |char|
      if hash_table.has_key?(char) then
        hash_table[char] = hash_table[char] + 1
      else
        hash_table[char] = 1
      end
    end

    slided_string.each_with_index do |char, i|
        if hash_table[char] == 1 then
            return i
        end
    end

    return -1

  else
    return -1
  end

end

---

Let's submit it and see the result.

Runtime: 612 ms, faster than 8.79% of Ruby online submissions for First Unique Character in a String.
Memory Usage: 14.4 MB, less than 10.00% of Ruby online submissions for First Unique Character in a String.

This is better but still pretty bad.

---

Solution 1.2

I don't like that we have 3 returns and I guess we can remove empty string checking.

def first_uniq_char(s)

    hash_table = {}
    slided_string = s.split("")

    slided_string.each do |char|
      if hash_table.has_key?(char) then
        hash_table[char] = hash_table[char] + 1
      else
        hash_table[char] = 1
      end
    end

    slided_string.each_with_index do |char, i|
        if hash_table[char] == 1 then
            return i
        end
    end

    return -1

end

---

Let's submit it and see the result.

Runtime: 476 ms, faster than 21.98% of Ruby online submissions for First Unique Character in a String.
Memory Usage: 14.4 MB, less than 10.00% of Ruby online submissions for First Unique Character in a String.

So far this is my best result.