First Non-Repeating Character

August 19, 2011

This question appears on several lists of interview questions:

Write a function that takes an input string and returns the first character from the string that is not repeated later in the string. For instance, the two letters “d” and “f” in the input string “aabcbcdeef” are non-repeating, and the function should return “d” since “f” appears later in the string. The function should return some indication if there are no non-repeating characters in the string.

Your task is to write the indicated function. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

62 Responses to “First Non-Repeating Character”

  1. uberlazy said

    Here’s a Clojure solution. Please note that, due to laziness, (first (filter… only evaluates up to the first non-repeating element.

    (defn freq [chars]                                                                                                                                                                                                                           
      (loop [chars chars freq {}]                                                                                                                                                                                                                
        (let [current (first chars)]                                                                                                                                                                                                             
          (if (empty? chars)                                                                                                                                                                                                                     
            freq                                                                                                                                                                                                                                 
            (recur (rest chars)                                                                                                                                                                                                                  
                   (assoc freq current (inc (or (freq current) 0))))))))                                                                                                                                                                         
                                                                                                                                                                                                                                                 
    (defn first-unique-char [chars]                                                                                                                                                                                                              
      (let [freqs (freq chars)]                                                                                                                                                                                                                  
        (first (filter #(= (freqs %) 1) chars))))  
    
  2. Erlend said

    A Haskell solution:

    import qualified Data.HashMap.Lazy as M -- from unordered-containers
    
    firstNonRep :: String -> Char
    firstNonRep =
        head . M.keys . M.filter (==1) . M.fromListWith (+) . map (\c -> (c,1))
    
    main = print $ firstNonRep "aabcbcdeef" == 'd'
    

  3. In C#:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace PP_20110819 {
    class Program {
    static void Main(string[] args) {

    Dictionary lookupTable = new Dictionary();

    for (int i = 0; i < args[0].Length; i++) {
    if (!lookupTable.ContainsKey(args[0][i])) {
    lookupTable[args[0][i]] = 1;
    } else {
    lookupTable[args[0][i]]++;
    }
    }

    for (int i = 0; i < args[0].Length; i++) {
    if (lookupTable[args[0][i]] == 1) {
    Console.WriteLine(string.Format("First non-repeating letter is {0}", args[0][i]));
    return;
    }
    }

    Console.WriteLine("There are no non-repeating letters.");

    }
    }
    }

  4. namespace PP_20110819 {
    class Program {
    static void Main(string[] args) {

    Dictionary<char, int> lookupTable = new Dictionary<char, int>();

    for (int i = 0; i < args[0].Length; i++) {
    if (!lookupTable.ContainsKey(args[0][i])) {
    lookupTable[args[0][i]] = 1;
    } else {
    lookupTable[args[0][i]]++;
    }
    }

    for (int i = 0; i < args[0].Length; i++) {
    if (lookupTable[args[0][i]] == 1) {
    Console.WriteLine(string.Format("First non-repeating letter is {0}", args[0][i]));
    return;
    }
    }

    Console.WriteLine("There are no non-repeating letters.");

    }
    }
    }

  5. Oh, Lord. Please let me delete misformatted comments…

  6. liesen said

    Erlend, your code fails this test: firstNonRep “faabcbcdeef” == ‘f’. (‘f’ moved to front of the input.) You rely on the order of the map.

    This, however, works: https://gist.github.com/1156886

  7. liesen said

    I shouldn’t have left the trailing ‘f’ in the test string above, of course.

  8. Here’s my clojure solution. More detail at my blog.

    ;;first non-repeating character
    (def test-str "aabcbcdeef")
    
    (defn find-non-repeat [some-str]
      (let [x (first
               (drop-while (fn [x] (> (count (last x)) 1))
                           (group-by identity some-str)))]
        (if (nil? x)
          "No non-repeating characters"
          (str (first x)))))
    
  9. kn said

    #include
    #include
    #include

    using namespace std;

    int FirstNonRepeatingCharacterIndex(string str)
    {
    int result = -1;

    set chars;

    for(int i = str.size() – 1; i >= 0; –i)
    {
    char c = str[i];

    if(chars.find(c) == chars.end())
    {
    result = i;
    }

    chars.insert(c);
    }

    return result;
    }

    int main()
    {
    string s(“aabcbcdeef”);
    int res = FirstNonRepeatingCharacterIndex(s);

    cout << "index:" <= 0)
    {
    cout << "\tcharacter: '" << s[res] << '\'';
    }

    cin.get();

    return 0;
    }

    returns:
    index:1 character: 'a'

  10. [...] today’s Programming Praxis exercise, our goal is to find the first character in a string that does not [...]

  11. My Haskell solution (see http://bonsaicode.wordpress.com/2011/08/19/programming-praxis-first-non-repeating-character/ for a version with comments):

    import Data.List
    import qualified Data.Map as M
    
    firstUnique :: Ord a => [a] -> Maybe a
    firstUnique xs = find (M.fromListWith (\_ _ -> False) (zip xs $ repeat True) M.!) xs
    
  12. Mike said

    Python 3 version

    from collections import Counter, OrderedDict
    
    class OrderedCounter(Counter, OrderedDict):
    	pass
    
    def first_unique(s):
    	oc = OrderedCounter(s)
    	return min(oc, key=oc.get)[0]
    
    first_unique("aabcbcdeef")
    #'d'
    first_unique("faabcbcdeef")
    #'d'
    first_unique("daabcbcdeef")
    #'f'
    
    
  13. Graham said

    My Python solution:

    def fst_non_rep(str):
        position = {}
        for i in xrange(len(str)):
            if str[i] not in position:
                position[str[i]] = i
            else:
                position.pop(str[i])
        try:
            return min(position, key=lambda k: position[k])
        except ValueError:            # All characters repeated
            return None
    

    Rather than make two passes through the whole string, I make one pass through
    the string and then one pass through all the unique characters (by calling min on
    the “position” dictionary). If there are few unique characters in the string, this may
    speed up the work significantly.

  14. Graham said

    @Mike: super slick answer, but I think you might run into trouble with strings
    in which all characters repeat—e.g. ‘aabbcc’—where it “should return some
    indication if there are no non-repeating characters in the string,” or with
    empty strings (perhaps a useless edgecase).

  15. Mike said

    Ignore my previous post; it doesn’t work right if there are no unique letters.
    Here is a correct solution.

    from collections import Counter, OrderedDict
    
    class OrderedCounter(Counter, OrderedDict):
    	pass
    
    def unique(s):
    	return (k for k,c in OrderedCounter(s).items() if c == 1)
    
    def first_unique(s):
    	return next(unique(s),'')
    
    
  16. bkyrlach said

    Here’s a Scala solution…

    @tailrec final def findNonRepeat(s:String):String = if(s.count(_ == s.first) > 1) findNonRepeat(s.tail.filterNot(_ == s.first)) else String valueOf (s.firstOption getOrElse “No non-repeating characters”)

  17. I’ve updated my answer based on some comments left on my blog. Here’s my new solution:

    ;;first non-repeating character
    (def test-str "aabcbcdeef")
    
    (defn find-non-repeat [some-str]
      (let [x (first
               (drop-while (fn [x] (> (count (last x)) 1))
                           (sort (group-by (fn [c] (.indexOf some-str (str c)))
                                           some-str))))]
        (if (nil? x)
          "No non-repeating characters"
          (str (first (last x))))))
    
  18. Why work when the library functions will work for you?
    C#:

    using System;
    using System.Linq;

    class Program
    {
    static void Main(string[] args)
    {
    string s = Console.In.ReadLine();
    try
    {
    char first = s.First(c => s.Count(x => x == c) == 1);
    Console.Out.WriteLine(“First nonrepeating letter: ” + first);
    }
    catch
    {
    Console.Out.WriteLine(“No nonrepeating letters.”);
    }
    }
    }

  19. pschorf said

    Clojure:

    (defn freq-map [string]
    (reduce #(assoc %1 %2 (+ (get %1 %2 0) 1)) (hash-map) string))

    (defn first-unique-char [string]
    (let [f-map (freq-map string)]
    (first (filter #(= 1 (get f-map %)) string))))

  20. bkyrlach said

    Here’s an even better Scala solution found with the help of some friends.

    final def findNonRepeat(s:String):String = String valueOf (s.drop(s.takeWhile(c => s.count(_ == c) > 1).size).firstOption getOrElse “No non-repeating characters” )

  21. Mike said

    @Graham. Just after I posted my first solution, I realized it didn’t work if there were no unique characters. The idea for the Ordered Counter came straight from the Python 3 documentation for OrderedDict, so I can’t take credit for that.

    I first tried a solution similar to yours. However, when a repeated letter is seen it is popped from the position dictionary–effectively “forgetting” that the letter had been seen. If a letter appears a third time, it will seem to be unique. Ex: fst_non_rep(‘ababac’) returns ‘a’ instead of ‘c’.

  22. Nathan said

    C# Linq solution. Minus all of the console crud and the all important answer.First();

    var answer = from c in input
    where input.IndexOf(c) == input.LastIndexOf(c)
    orderby input.IndexOf(c)
    select c;

  23. clojure version using frequences:

    (defn first -unique-char [s]
      (let [f-map (frequencies s)]
        (first (filter #(= 1 (get f-map  %)) s))))
    
  24. Graham said

    @Mike: fair enough, thanks for pointing out my mistake! I was trying to minimize the work on the second run, but didn’t think hard enough, apparently. I think your Ordered Counter takes the cake :-)

  25. In Clojure, also with frequencies, and golfing a bit:

    (defn first-unique [s] (ffirst (filter #(= 1 (second %)) (frequencies s))))

  26. vukung said

    (defun first-non-repeated (str)
    (let ((freq (map ‘list (lambda (c) (cons (count c str) c)) str)))
    (cdar (member 1 freq :key #’car))))

  27. ram said

    there is a natural unfair advantage to perl programmers
    In perl I can write the entire logic in 3 lines
    perfectly readable code … Assume $str is the string input

    foreach my $c ($str =~/(.)/g){
    @uniq = ($seen{$c}++) ? grep{!/$c/} @uniq : (@uniq,$c);
    }
    print $uniq[0] . “\n”,

    take the foreach also inline and implement the logic in 1 line .. But i guess that makes code unreadable

  28. scottdw said
    (defn fnrc [s]
      (println (if-let [c (first (filter
                                  (set (map first (filter (comp #{1} second)
                                                          (frequencies s))))
                                  s))]
                 (str "The first non-repeating character is: " c)
                 "No non-repeating character found.")))
    
  29. #include
    #include
    #include

    int main () {

    char str[80];
    char str_a[80];
    int l, i;
    char c;

    printf(“Please enter the string to find non-repeating char\n”);
    scanf(“%s”,str);
    l = strlen(str);

    for (i = 0; i < l ; i++) {
    c = str[i];
    //copy rest of the string except char 'c' into another
    memcpy(&str_a[0] , &str[0], i);
    memcpy(&str_a[i] , &str[i+1], (l-i-1));
    if (!strchr(str_a, c)) {
    printf("First non repeating char in string : \"%c\"\n",c);
    break;
    }
    }
    if (i == l)
    printf("Non repeating char not found in given string\n");
    }

  30. slabounty said

    In ruby …

    def first_nonrepeat(s)
        nonrepeat = []
        repeat = []
        s.each_char do |c|
            if !repeat.include?(c) && !nonrepeat.include?(c)
                nonrepeat << c
            elsif nonrepeat.include?(c)
                nonrepeat.delete(c)
                repeat << c
            end
        end
        return !nonrepeat.empty? ? nonrepeat.first : ""
    end
    

    If a character is not on either the repeat or nonrepeat lists, add it to the nonrepeat. If it’s on the nonrepeat, remove it and add it to the repeat list, otherwise we’ve already seen it and it’s on the repeat list already. Return either the first item on the nonrepeat list if it’s not empty or the empty string if it is. I think this should work in all cases. We’re letting the ruby array class do all the hard work here.

  31. Simone said

    My C solution. Cost of the algorithm: O(2*stringlength)

    #include <stdio.h>
    
    #define ALPHABET_LENGTH 256
    
    int main()
    {
    	short cc[ALPHABET_LENGTH];
    	int i;
    	char *str="abcdefgghabcdeklortolkrtw", *t;
    
    	for(i=0;i<ALPHABET_LENGTH;i++)
    		cc[i]=0;
    
    	for(t=str;*t;t++)
    		cc[*t]++;
    
    	for(t=str;*t;t++){
    		if(cc[*t]==1){
    			printf("letter %c\n", *t);
    			return;
    		}
    	}
    
    	printf("nothing\n");
    
    	return 0;
    }
    
  32. wesen said

    @crkirkendall @Alan @vukung those don’t work:

    user> (first-unique-char “aabbcddeeffc”)
    nil
    user> (first-unique “aabbcddeeffc”)
    nil

    My verbosey clojure solution (new to clojure, coming from them common lisp):


    (defn first-non-repeating [str]
    (loop [c (first str)
    cnt 1
    [n & str] (rest str)]
    (cond
    (nil? c) nil
    (and (not= c n) (= cnt 1)) c
    (not= c n) (recur n 1 str)
    true (recur c (inc cnt) str))))

  33. wesen said

    More idiomatic clojure:

    (defn first-unique [str]
      (ffirst (filter #(= (count %) 1) (partition-by identity str))))
    
  34. module Solution where

    import List

    solution :: String -> IO ()
    solution a =
    case reduce a of
    [] -> putStrLn “No repeating characters!”
    (x:_) -> putStrLn $ “Solution: ” ++ x
    where
    reduce = filter (\x -> length x == 1) . group . sort

  35. Curious if this works…

  36. @Clint Moore: Your code returns the alphabetically first non-repeating character, not the first according to the input string.

    Example: For “fa” your code will give ‘a’, but the solution should give ‘f’.

  37. Axio said

    Basically Gambit-C with extensions…
    Recursively construct an occurrences table, and when returning, check if head of intermediate list as only one occurrence (guaranteeing the “first” unique element will be returned). Returns “#f” if no unique char.
    A bit verbose, but pretty direct.
    Basically, O(n).

    (define (fnrc-aux l h)
      (if (null? l)
        (values #f h)
        (call-with-values
          (lambda ()
            (table-modify! h (car l) succ 1)
            (fnrc-aux (cdr l) h))
          (lambda (char tab)
            (if (= 1 (table-ref tab (car l)))
              (values (car l) tab)
              (values char tab))))))
    
    (define (fnrc str)
      (call-with-values
        (lambda ()
          (fnrc-aux (string->list str) (make-table)))
        (lambda (char _)
          char)))
    
  38. Chicken scheme: this seems to work…

    (define (non-rep-char str)
    (let lp ((ls (string->list str)) (chrs ‘()))
    (cond
    ((null? ls)
    (print “No non-repeating chars.”)
    done:)

    ((member (car ls) chrs)
    (lp (cdr ls) chrs))

    ((member (car ls) (cdr ls))
    (lp (cdr ls) (cons (car ls) chrs)))

    (else
    (car ls)))))

  39. Martin said

    Hey!
    Just found this site through sixrevisions.com and thought I might have a try on one of the puzzles! So I’m a student in java-programming among other stuff, so that’s the language I used for my solution. Here goes:

    package nonRepeat;

    import java.util.Scanner;

    public class NonRepeatMain
    {
    public static void main(String[]args)
    {
    System.out.print(“Input string to check: “);
    String result=new NonRepeatMain().checkString(new Scanner(System.in).nextLine().toCharArray());
    if(result==null)
    {System.out.print(“No unique character in the string.”);}
    else
    {System.out.println(“‘”+result+”‘ is the first unique character.”);}
    }
    private String checkString(char[] text)
    {
    boolean unique;
    for(int i=0;i<text.length;i++)
    {
    unique=true;
    for(int j=0;j<text.length;j++)
    {
    if(j!=i)
    {
    if(text[i]==text[j])
    {
    unique=false;
    break;
    }
    }
    }
    if(unique==true)
    {return Character.toString(text[i]);}
    }
    return null;
    }
    }

    Pretty straightforward (I think?), don't know if I could have made this more effective in some way, as I've just been studying programming for less than a year.

  40. Adolfo said

    Here is my Racket solution. I’ve used two tables to map each character to the number of occurrences (and viceversa); this way, it is possible to solve this with no conditionals (with the exception of the implicit one in the “for” construct) and traversing the string only once.

    #lang racket

    (define max-word-length 20)

    (define (chars-repeating-times str n)
    (let ((freq-table (make-vector max-word-length ‘()))
    (char-table (make-hash)))
    (for ((c (in-string str)))
    (let* ((previous-count (hash-ref char-table c 0))
    (next-count (add1 previous-count)))
    (vector-set! freq-table previous-count
    (remove c (vector-ref freq-table previous-count)))
    (vector-set! freq-table next-count
    (cons c (vector-ref freq-table next-count)))
    (hash-set! char-table c next-count)))
    (reverse (vector-ref freq-table n))))

    (define (first-non-repeating-char str)
    (first (chars-repeating-times str 1)))

    (require rackunit)

    (check-equal? (chars-repeating-times “” 1) ‘())
    (check-equal? (chars-repeating-times “a” 1) ‘(#\a))
    (check-equal? (chars-repeating-times “aabccd” 1) ‘(#\b #\d))
    (check-equal? (chars-repeating-times “aabbcc” 1) ‘())

  41. spirit said

    // This is the javascript version

    function getFirstUniqueChar(s) {
    var map = (function(map, len, i, c) {
    while (i < len) map[c = s.charAt(i++)] = map[c] ? (map[c] + 1) : 1;
    return map;
    }({}, s.length, 0));

    for (key in map) {
    if (map[key] == 1) return key;
    }

    return -1;
    }

  42. anon said

    A version in prolog that operates on lists:


    non_repeating(Atom,List) :-
            select(Atom,List,Rest), not(member(Atom,Rest)).
    first_non_repeating(Atom,List) :-
            non_repeating(Atom,List), !.

  43. Kal Nasser said

    Java:

    public static char firstNonRepeatingCharacter(String s) {
    for (int i = 0; i < s.length() – 1; i++) {
    if (s.lastIndexOf(s.charAt(i)) == i) {
    return s.charAt(i);
    }
    }
    return '';
    }

  44. anon said

    @Karl Nasser:
    what does firstNonRepeatingCharacter(“aa”) return?

  45. tarun said

    #include
    #include

    #define MAX 10
    void check(char *k)
    {
    int i,j,l=0,d,it=0;
    int index[20];
    int s=0,len=0,p=0,st=0;
    for(d=0;d<strlen(k);d++)
    {
    for(i=d,j=i+1;j<strlen(k);j++)
    {
    if(k[i]==k[j])
    {
    index[s]=i;
    s=s+1;
    index[s]=j;
    len=len+2;
    s=s+1;
    }
    }
    index[s]=-1;
    len++;
    s++;
    }
    for(st=0;st<len;st++)
    {
    if(index[st]!=-1)
    {
    p=index[st];
    k[p]='0';
    }
    }
    for(it=0;it<strlen(k);it++)
    {
    if(k[it]!='0')
    {
    printf("%c",k[it]);
    break;
    }
    }
    if(it==strlen(k))
    printf("every charater in di string is repeated:");

    }
    void main()
    {
    char ch[11]="aabcbcdeef";
    check(ch);
    }

  46. Vinit Bhandari said

    Python code:

    def first(str):
    for i in xrange(0, len(str)):
    if str[i] not in str[:i] + str[i+1:]:
    return str[i]
    return “No element unique!”

    #test code
    #print first(‘kkkojlooouoojlv’)
    #prints ‘u’

  47. fa said

    A different approach is to split the parsed characters into two sets, RC – containing repeating characters and NRC – containing not repeating characters.
    First look at RC, if the character is there, go next. Otherwise, if the character is in NRC, move it to RC and go next. Otherwise put the character in NRC.. and go next.
    NRC can be ordered by combining an hashset with a double linked list, so the first not repeating character is the first one left in NRC.
    The resulting function parses the string only once at the cost of a bit more complex data structure.

    FirstNonRepeatingCharacter.java

    /home/fabio/Desktop/Prog/programming praxis/first non repeating character/FirstNonRepeatingCharacter.java

     1 import java.util.HashSet;
     2 import java.util.LinkedHashSet; // is insertion ordered
     3 
     4 public class FirstNonRepeatingCharacter
     5 {
     6     /**
     7         Get the first non repeating character of a string.
     8         This function parses the input string in one single pass.
     9         @param aStr the string to parse
    10         @return the first not repeating character or null
    11     */
    12     public static Character fnr(String aStr) {
    13         final int len = aStr.length();
    14         LinkedHashSet<Character> notRepChars = new LinkedHashSet<Character>(len);
    15         HashSet<Character> repChars = new HashSet<Character>(len);
    16 
    17         for (int i = 0; i < len; i++) {
    18             Character ch = aStr.charAt(i);
    19             
    20             if (repChars.contains(ch)) continue;
    21             if (notRepChars.contains(ch)) {
    22                 notRepChars.remove(ch);
    23                 repChars.add(ch);
    24             } else notRepChars.add(ch);
    25         }
    26         return notRepChars.isEmpty() ? null : notRepChars.iterator().next();
    27     }
    28     
    29     /**
    30         Print the first not repeating character of each argument.
    31     */
    32     public static void main(String args[]) {
    33         for (String str : args)  System.out.println(fnr(str));
    34     }
    35 }
    36 
    37 
    
  48. Bostan Fericit said

    In Java.

    public static int firstNonRepeatingCharacter(char[] chars) {
    boolean found;

    for (int i = 0; i < chars.length; i++) {
    found = false;

    for (int j = 0; j < chars.length; j++) {
    found = (i != j) && (chars[i] == chars[j]);

    if (found) {
    break;
    }
    }

    if (!found) {
    return chars[i];
    }
    }

    return -1;
    }

  49. steve said

    All posted solutions I saw are incorrect, because they only work with a small number of characters and don’t work with diacritical marks.
    C’mon, it isn’t 1970 anymore, use Unicode!

  50. Bostan Fericit said

    Hi Steve,

    I’ve run my solution with unicode characters and it works correctly. But perhaps I am overlooking something. Can you provide me with some sample data that will show me what I might be missing?

    public class NonRepeating {
    public static void main(String[] args) {
    printFirstNonRepeatingCharacter(“test1″, “aabbccdeeff”);
    printFirstNonRepeatingCharacter(“test2″, “xdtàxadt㊨”);
    printFirstNonRepeatingCharacter(“testUnicode”,
    “\uDFFF\u0025\u0029\u0041\uDFFF\u0025″);
    }

    private static void printFirstNonRepeatingCharacter(String name, String str) {
    int c = getFirstNonRepeatingCharacter(str.toCharArray());
    if (c > 0) {
    System.out.printf(“%s: %c%n”, name, c);
    }
    else {
    System.out.printf(“%s: no non-repeating character found!%n”, name);
    }
    }

    public static int getFirstNonRepeatingCharacter(char[] chars) {
    boolean found;

    for (int i = 0; i < chars.length; i++) {
    found = false;
    for (int j = 0; j < chars.length; j++) {
    found = (i != j) && (chars[i] == chars[j]);

    if (found)
    break;
    }

    if (!found)
    return chars[i];
    }

    return -1;
    }
    }

  51. fa said

    @steve

    1. for example:

    $ ./fnrc "рработает" "aaxxèè ø  ggg11°°°"
    б
    ø
    $ 
    

    2. it doesn’t matter..

  52. Bostan Fericit said

    Using your sample data my solution does return the correct data, based upon what you have shown above.

  53. Q&D PLT Racket version. Though, except for the first two Racket-specific lines, I think it’d work in just about any scheme that has SRFI 13.

    #lang scheme
    (require srfi/13)
    
    (define (first-non-repeating-character s)
      (string-any (lambda (c)
                    (if (= 1 (string-count s c))
                        c
                        #f))
                  s))
    
    (first-non-repeating-character "")
    (first-non-repeating-character "aabbccddeeff")
    (first-non-repeating-character "aabcbcdeef")
    (first-non-repeating-character "faabcbcdee")
    
  54. mrjbq7 said

    How about some Factor!

    : first-non-repeat ( seq -- elt )
        dup histogram [ at 1 = ] curry find nip ;
    

    And some tests to show it works:

    [ f ] [ "" first-non-repeat ] unit-test
    [ CHAR: a ] [ "abc" first-non-repeat ] unit-test
    [ f ] [ "aabbcc" first-non-repeat ] unit-test
    [ CHAR: d ] [ "aassdf" first-non-repeat ] unit-test
    
  55. jyoti aditya said

    #include
    #include

    void main()
    {
    int i=0,f=0,g,h,j=0,k=0,l=0,len;
    char str[100],ch;
    printf(“\n\n enter the string\n”);
    gets(str);
    len=strlen(str);
    while(i<len)
    { g=0;h=0;
    while(j<len)
    {
    if(str[i]=='*')
    {
    i++;
    j=i;
    continue;
    }
    if(str[i]==str[j+1])
    {
    str[j+1]='*';
    j++;
    h=1;
    continue;
    }
    else
    {
    j++;

    if(h==0&&j==len)
    {
    printf("\nthis is first character in string which is nonrepeating\n");
    printf("%c",str[i]);
    g=1;f=1 ;
    break;
    }
    }
    }
    i++;
    j=i;
    if(g==1)
    break;
    }
    if(f==0)
    printf("\nthere is no nonreapeating character\n");

    }

  56. Josh T said

    This PLT Scheme / Racket solution won’t be notably fast, but I think it’s worth sharing for its brevity.

    (But here’s a GitHub gist for nicer presentation.)


    (define (first-uniq chars)
    (when (empty? chars)
    (raise "There are no unique letters"))
    (let ([c (first chars)])
    (if (memq c (rest chars)) ; MEMQ is like MEMBER but uses EQ?
    (first-uniq (remq* (list c) chars))
    c)))

    ; test it
    (if (equal? #\d (first-uniq (string->list "aabcbcdeef")))
    (display "SUCCESS!!!")
    (display "aw, darn."))

  57. Here’s a functional solution in Racket that runs in linear time:

    #lang racket
    (require rackunit)
    
    (define (first-non-repeating-char str)
      (let ((counts (for/fold ((dict (hash))) ((char str))
                      (hash-update dict char add1 0))))
        (for/first ((char str) #:when (= (dict-ref counts char) 1))
          char)))
    
    (check-equal? (first-non-repeating-char "") #f)
    (check-equal? (first-non-repeating-char "abab") #f)
    (check-equal? (first-non-repeating-char "aabcbcdeef") #\d)
    
  58. GDean said

    b<-c(1,2,3,4,5,6,1,2,3,4,5,6,7) #base string, contains integers 1 and greater

    n<-length(b)
    bprime<-b
    for (i in 1:(n-1)) {
    for (j in (i+1):n) {
    if (b[i]==b[j]) {
    for (a in 1:n) {
    if (b[a]==b[i]) {
    bprime[a]<-0
    }
    }
    }
    }
    }

    count<-0
    for (e in 1:n) {
    if (bprime[e]==0) {
    count<-count+1
    }
    }

    if (count==n) {
    print("ERROR: no non-repeating characters")
    }

    #Now print the first non-repeating character from the input string

    for (p in 1:n) {
    if ((bprime[p])!=0) {
    print(bprime[p])
    break
    }
    }

  59. cosmin said

    A linear solution with O(1) extra-space avoiding the second iteration.

    def first_non_dup(a):
    	pos = [None]*256
    	for i, c in enumerate(a):
    		pos[ord(c)] = i if pos[ord(c)] == None else -1
    	minindex = None
    	for i in xrange(256):
    		if pos[i] == None or pos[i] == -1: continue
    		if minindex == None or pos[i] < pos[minindex]: minindex = i
    	return None if minindex == None else chr(minindex)
    
    print first_non_dup("aabcbcdeef")
    
  60. Kal Nasser said

    Oops. Ignore my first solution from two years ago :) A readable Linq solution, first getting a list of unique characters, then returning the first one, if any.

    char? FirstNonRepeatingCharacter(String str) 
    {
    	var UniqueCharacters = 
    			from character in str
    			group character by character into grp
    			where grp.Count() == 1
    			select grp.Key;		   
    
    	return (UniqueCharacters.Any() ? UniqueCharacters.First() : (char?) null);
    }
    
  61. steve said

    Thanks for this code. I’m gonna take a look at it and try some of these examples for myself. However, I am a noob at coding and these do seem a tadge complex. Keep up the good work. Cheers :-)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 627 other followers

%d bloggers like this: