Find the first un-repeated character in a string

by

It has to be at least O(n) because you don’t know if a character will be repeated until you’ve read all characters.

So you can iterate over the characters and append each character to a list the first time you see it, and separately keep a count of how many times you’ve seen it (in fact the only values that matter for the count is “0”, “1” or “more than 1”).

When you reach the end of the string you just have to find the first character in the list that has a count of exactly one.

Example code in Python:

def first_non_repeated_character(s):
    counts = defaultdict(int)
    l = []
    for c in s:
        counts[c] += 1
        if counts[c] == 1:
            l.append(c)

    for c in l:
        if counts[c] == 1:
            return c

    return None

This runs in O(n).

More Related Contents:

  1. How can I pair socks from a pile efficiently?
  2. Unique (non-repeating) random numbers in O(1)?
  3. Ukkonen’s suffix tree algorithm in plain English
  4. Converting a Uniform Distribution to a Normal Distribution
  5. Can hash tables really be O(1)?
  6. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  7. What distribution do you get from this broken random shuffle?
  8. Is there an O(n) integer sorting algorithm?
  9. Determine font color based on background color
  10. Nearest neighbors in high-dimensional data?
  11. What algorithm gives suggestions in a spell checker?
  12. How can I measure the similarity between two images? [closed]
  13. Generate all unique substrings for given string
  14. Sum-subset with a fixed subset size
  15. What is a good Hash Function?
  16. design a stack such that getMinimum( ) should be O(1)
  17. Binary Search in Array
  18. How to check if line segment intersects a rectangle?
  19. What string similarity algorithms are there?
  20. Calculate largest inscribed rectangle in a rotated rectangle
  21. Algorithm to find multiple string matches
  22. The Sieve of Atkin
  23. How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?
  24. 3 dimensional bin packing algorithms
  25. Find 2 numbers in an unsorted array equal to a given sum
  26. Algorithm to find the most common substrings in a string
  27. “Rounding” colour values to the nearest of a small set of colours
  28. Word comparison algorithm
  29. How to convert decimal fractions to hexadecimal fractions?
  30. Best algorithm for matching colours.

Leave a Comment