Algorithmathon Day 12: String First Non-repeated Character

Created: 26 July 2013  Modified:

This entry starts a period of string manipulation. Today’s goal will be to return the first non-repeated character in a string. Ruby provides us with a String class that will be easy to subclass. If we have string “ABABCAB” we want to find the letter “C”. One way to approach this is to compare every letter in the string to every other letter in the string. This however would have a n2 cost. If we shortened the string by one character on each pass we could reduce that to n * (n-1). Faster but still effectively n2. If however we use a hash to track and count the letters we can reduce this to n + 26. In this case we are assuming the use of only A through Z. Let’s jump right into the initial RSpec tests.

algorithm_string_spec.rb

require 'spec_helper'

describe AlgorithmString do

  describe "Class" do
    it "should have method 'first_nonrepeated'" do
      AlgorithmString.method_defined?(:first_nonrepeated).should be_true
    end
  end

  describe "Instance" do

    before(:each) do
      @string = AlgorithmString.new()
    end

    it "should not be nil" do
      @string.should_not be_nil
    end

  end

end

A very basic class will satisfy these tests.

algorithm_string.rb

class AlgorithmString < String
  def first_nonrepeated()
    
  end
end

Now we need something with more substance so lets build some additional tests and the code to satisfy them.

algorithm_string_spec.rb (excerpt)

  #code omitted here
    it "should return nil when 'first_nonrepeated()' method is called" do
      @string.first_nonrepeated().should_not be_nil
    end

    it "should return nil when 'first_nonrepeated()' method is called" do
      @string.first_nonrepeated().should == 'C'
    end
  #code omitted here

algorithm_string.rb

class AlgorithmString < String
  def first_nonrepeated()
    string_array=self.to_s.split(//)
    character_count=Hash.new()
    return_value=nil
    string_array.each_with_index { | character_outer, index |
      if character_count[character_outer].nil?
         character_count[character_outer] = 1
      else
        character_count[character_outer] = character_count[character_outer] + 1
      end
    }
    character_count.each { | key, value |
      if value < 2
        return_value=key
      end
    }
    return_value
  end
end

We now have a working method that gives us a solution. Next time we will be adding a method which removes characters from a string.

tags: Algorithm - Algorithmathon - RSpec - Ruby - String
   Less Is More