Problem of the Day
A new programming or logic puzzle every Mon-Fri

No-repeat

Today's objective is to create a function that takes in a string and returns the first non-repeated character. For instance, in the string 'abcdab', your function should return 'c'. Bonus points for a solution that solves this in linear run time.

Permalink: http://problemotd.com/problem/no-repeat/

Comments:

  • Foppe - 10 years, 2 months ago

    #! /usr/bin/pyhon
    
    import sys
    
    input_string = sys.argv[1]
    
    chars_possible = []
    chars_rejected = []
    
    for i_char in input_string:
        if i_char in chars_rejected:
            continue
        elif i_char in i_chars_possible:
            chars_possible.remove(i_char)
            chars_rejected.append(i_char)
        else:
            chars_possible.append(i_char)
    
    print("Found %s" % chars_possible[0])
    

    reply permalink

  • Chuisi - 10 years, 2 months ago

    Similar but using dictionaries to provide linear insertion and search times to drop the overall time from O(n2 ) to O(n)

    #! /usr/bin/python
    
    import sys
    
    def f(string):
        chars = {}
        for char in string:
            if char in chars:
                chars[char] = False
            else:
                chars[char] = True
    
        for char in string:
            if chars[char] == True:
                return char
    
    print(f(sys.argv[1]))
    

    reply permalink

  • Driphter - 10 years, 2 months ago

    Clojure!

    (defn first-non-repeating [x]
      (->> x
           frequencies
           (filter #(= 1 (second %)))
           first
           first))
    
    ; user=> (first-non-repeating "abcdab")
    ; \c
    
    

    reply permalink

  • Driphter - 10 years, 2 months ago

    c#

    char? FirstNonRepeating(string value)
    {
        var chars = new Dictionary<char, bool>();
    
        foreach (var c in value)
            if (chars.ContainsKey(c))
                chars[c] = false;
            else
                chars.Add(c, true);
    
        foreach (var c in chars)
            if (c.Value)
                return c.Key;
    
        return null;
    }
    

    c# (Linq)

    static IDictionary<TSource, int> Frequencies<TSource>(this IEnumerable<TSource> source)
    {
        var counts = new Dictionary<TSource, int>();
        foreach (var element in source)
            if (counts.ContainsKey(element))
                counts[element]++;
            else
                counts.Add(element, 1);
        return counts;
    }
    
    static TSource FirstNonRepeating<TSource>(this IEnumerable<TSource> source)
    {
        return source.Frequencies()
                     .FirstOrDefault(x => x.Value == 1)
                     .Key;
    }
    

    reply permalink

  • rossthebossperot - 10 years, 2 months ago

    Python. Pretty sure this would be linear. I'm not 100% clear how Python's string.count function works.

    string = input('Type a string> ')
    
    for x in string:
        if string.count(x) == 1:
            print(x)
            break
    

    reply permalink

  • Max Burstein - 10 years, 2 months ago

    I don't think this would find the first repeated character though I'm not sure about string.count either. You could run in to a case like 'abaab' where a is still the right answer.

    reply permalink

  • Walker Crouse - 10 years, 2 months ago

    def no_repeat(s):
        for i in range(0, len(s)):
            sub = s[i+1:]
            if sub is not None and sub and s[i] not in sub:
                return s[i]
        return None
    
    
    def main():
        print('First non-repeating character : "' + 
              str(no_repeat(input("Enter a string to process : "))) + '"')
    
    
    if __name__ == "__main__":
        main()
    

    reply permalink

  • asheehan - 10 years, 2 months ago

    in Ruby

    s = 'abcdcbdq'
    
    possible = Array.new
    duplicate = Hash.new
    
    s.each_char do |x|
        if !duplicate[x]
            i = possible.index(x)
            if i
                duplicate[x] = true
                possible.delete_at(i)
            else
                possible.push(x)
            end
        end
    end
    
    puts possible.first
    

    reply permalink

Content curated by @MaxBurstein