How can I find the first non-repeating character in a string?

Question

I need to write a function that returns the first non-repeating character in a string (case insensitive). For example, for a string "Thanks for visiting"should be returned "h".

Answer 1

You can pass characters in a string and store counters for each character (case insensitive) in a hash. Then make another pass and return the first character with a score of 1:

sub get_char {
    my ($string) = @_;
    my @chars = split //, $string;
    my %chars;
    ++$chars{ lc() } for @chars;
    $chars{ lc() } == 1 && return $_ for @chars;
}

Apparently, this approach takes O(n)time and O(n)additional space.

Answer 2

sub { 
    # This assumes non-repeating means consecutive-repeating.
    # non-consecutive-repeating is too boring to answer
    my $string_copy = $_[0];
    $string_copy =~ s/(.)(\1)+//g; 
    return substr($string_copy ,0, 1)
}  

Answer 3

import java.io.BufferedReader;
import java.io.InputStreamReader;


/**
 * Myinterview class demonstrating how one can implement an algorithm 
 * that returns the first occurance of a char value in a string object
 * known issues: none 
 * @author collenn
 *
 */
public class MyInterview {

    public static void main (String[] args){
        MyInterview myInterview = new MyInterview();

        try{
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));   
            System.out.println("\n\t Please, enter a string to test algorithm ");
            System.out.print("Input String = ");
            String inputString = in.readLine();
            myInterview.findFirstNonRepeatingChar(inputString);
        }catch (Exception e) {
            e.printStackTrace();
        }
    }

/**
 * 
 * @param str
 * @return
 */
    private char findFirstNonRepeatingChar(String str){
        String nextSearcheableStr = str;
        StringBuilder sb = new StringBuilder(nextSearcheableStr);
        StringBuilder sb2 = null;
        char c = 0;
        int index = 0;

        while( sb.length()> 1){
            if (index > 0){
                sb = sb2;
            }
            c = sb.charAt(index);
            // and now the magic method
            if(!isCharRepeated(sb.toString(),c,index)){     
                System.out.println("First non recurring charactor is :" + c);
                return c;
            }
            else{
                // increase start position for next iteration use a char (*) place holder
                index = index +1;
                str  = str.replace(c,'*').trim();
                sb2 = new StringBuilder(str.replace(c,'*').trim());
            }
        }
        return c;       
    }
/**
 * This "magic" method determines whether a char value is repeated more than once 
 * in a string object.
 * @param str
 * @param c
 * @param x
 * @return boolean true if char is repeated 
 */
public boolean isCharRepeated(String str, char c, int x){
    boolean isRepeated = false;
    char[] cc = str.substring(x,str.length()).toCharArray();
    for (int i = 1; i < cc.length; i++) {
        if (cc[i]==c | c == '*'){
            isRepeated = true;
            return isRepeated;
        }
    }
    return isRepeated; 
}
}

Answer 4

substr() index():

sub get_it {
    my $string = shift;
    for my $i ( 0 .. length($string) - 1 ) {
        my $char = substr $string, $i, 1;
        return $char if index( $string, $char, $i + 1 ) >= 0;
    }
}

Answer 5

com.msa.interview;

public class MyNonRepatativeCharFinderClass {

/**
 * @param args
 */
public static void main(String[] args) {

String str="Google";
    int[]count =new int[128];
    char []charArr=str.toLowerCase().toCharArray();
    for(char c: charArr){
        count[c]++;

    }
    for(char c:charArr){
        if(count[c]==1){
            System.out.println("First Non repatated element in array: " +c);
            break;
        }

    }
}

}