Posted in ruby

Uniqueness Matters: Detecting Duplicate Characters in Ruby with Space-Efficiency

   January 30, 2024
Ruby @ Freshers.in

Detecting unique characters in a string is a common programming task, often used in applications like data validation and duplicate detection. In this article, we’ll explore how to write a Ruby function to determine if a string has all unique characters, and we’ll even provide a bonus by optimizing for space efficiency.

Understanding the Problem

The task at hand is to examine a given string and determine whether it contains any duplicate characters. For instance, in the string “programming,” the letter “g” appears twice, so it does not consist of all unique characters.

The Ruby Function (Naive Approach)

Let’s start by defining a Ruby function called has_unique_characters using a straightforward approach:

def has_unique_characters(str)
  char_set = Set.new

  str.each_char do |char|
    return false if char_set.include?(char)
    char_set.add(char)
  end

  return true
end

Example Usage (Naive Approach)

Now, let’s explore some examples to see how our has_unique_characters function works:

input_str_1 = "programming"
result_1 = has_unique_characters(input_str_1)
puts "Input String: #{input_str_1}"
puts "All unique characters? #{result_1}"

In this example, “programming” does not consist of all unique characters, so the function returns false.

The Ruby Function (Space-Efficient Approach)

To optimize for space efficiency, we can avoid using a Set data structure and instead use a bit vector (assuming the string contains only lowercase letters a-z). This approach is space-efficient because it uses a fixed amount of memory:

def has_unique_characters_space_efficient(str)
  checker = 0
  str.each_char do |char|
    char_val = char.ord - 'a'.ord
    mask = 1 << char_val
    return false if (checker & mask) > 0
    checker |= mask
  end
  return true
end

Example Usage (Space-Efficient Approach)

Now, let’s explore some examples using our space-efficient function:

input_str_2 = "algorithm"
result_2 = has_unique_characters_space_efficient(input_str_2)
puts "Input String: #{input_str_2}"
puts "All unique characters? #{result_2}"

Output (Space-Efficient Approach):

Input String: algorithm
All unique characters? true

In this example, “algorithm” consists of all unique characters, so the space-efficient function returns true.

Post Views: 0
Author: user
Website