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

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.

Comments:

• Foppe - 11 years 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 - 11 years ago

  Similar but using dictionaries to provide linear insertion and search times to drop the overall time from O(n² ) 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 - 11 years ago

  Clojure!

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

  reply permalink

• Driphter - 11 years 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 - 11 years 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 - 11 years 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 - 11 years 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 - 11 years 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