August 20, 2010

First non repeating character hash

By Mohammed Abualrob Algorithms and Data Structures 0 Comments

Problem

Develop an algorithm to print the first none repeating character in a string for example the first none repeating character in the string “baby” is “a”

Hash character in string

This is a typical interview question. A better solution to solve this problem in linear time is to use a hash table on the expense of extra space. Scan the string character by character from left to right while hashing the character. Then scan the hash table looking for the first character that has a count of one.

Code

Here is how to do it in Perl

# Input strings
$str1 = "baby";
$str2 = "bus";
$str3 = "ooo";

# Call function
print "First none repeating char of $str1 is: ";
&FirstNoneRepeating($str1);
print "First none repeating char of $str2 is: ";
&FirstNoneRepeating($str2);
print "First none repeating char of $str3 is: ";
&FirstNoneRepeating($str3);

# Function receives input string
sub FirstNoneRepeating
{
   # Input parameter
   my ($str) = @_;

   # Get characters
   @chars = split ('', $str);
   # Hash data structure
   %H = ();

   # Add the chars to the hash table
   foreach $char (@chars)
   {
      # char is used as the key
      # and the value is the count
      # of that char in the string
      # Duplicate chars hash to the
      # same spot
      $H{$char}++;
   }

   # Search the Hash for the first
   # none repeating character
   foreach $char (@chars)
   {
     if ($H{$char} == 1)
     {
        print "$char\\n";
        last;
     }
   }
}

# Input strings

$str1 = "baby";

$str2 = "bus";

$str3 = "ooo";

# Call function

print "First none repeating char of $str1 is: ";

&FirstNoneRepeating($str1);

print "First none repeating char of $str2 is: ";

&FirstNoneRepeating($str2);

print "First none repeating char of $str3 is: ";

&FirstNoneRepeating($str3);

# Function receives input string

sub FirstNoneRepeating

{

# Input parameter

my ($str) = @_;

# Get characters

@chars = split ('', $str);

# Hash data structure

%H = ();

# Add the chars to the hash table

foreach $char (@chars)

{

# char is used as the key

# and the value is the count

# of that char in the string

# Duplicate chars hash to the

# same spot

$H{$char}++;

}

# Search the Hash for the first

# none repeating character

foreach $char (@chars)

{

if ($H{$char} == 1)

{

print "$char\\n";

last;

}

Thanks for visiting. Please use the comments section below for feedback.

8 BIT AVENUE

First non repeating character hash

More from my site

About Author

Mohammed Abualrob

Add a Comment