Programming Questions

  • Newest
  • Popular Tags
  • Ask Question
  • Most frequent char in a string
    Hi, I was wondering how you guys find the most frequent character in a string. I'm trying to find the simplest way which also has the best performance. Currently, I use a dict to count the occurrences and sort it by values. Which is O(nlogn). What about you guys?
    cmgaba posted this question on 12/20/13 | python, algorithms
  • +
  • 2
  • -
  • The way I would do it, which would be O(n), would be to create a 256-element array of ints (for all 256 potential ASCII characters). You really only need 122, since 'z' is ASCII 122, but either way, 256 to keep it simple (since it's really not too crazy of space usage). This creation step is O(1). Then, I would do a for loop through each character of the string, incrementing the element of my array at the index of the ASCII value of that character (if you want to be case insensitive, you can just do a simple if-statement check and add 32 to make an uppercase letter lowercase, or subtract 32 to make a lowercase letter uppercase). This step would be O(n), because the incrementing is constant time. Then, I would iterate through the int array to find the index with the largest value at it, and cast that int index as a char, and that's the ASCII character that's most frequent! This last step always takes 256 steps, no matter what n is, so it's O(1). This method would be inefficient for small strings, but for very large ones (or especially file input perhaps? like a text file?), it would be pretty efficient relatively speaking.
  • +
  • 0
  • -
  • I would do it like this:
    max = 0
    for i in string:
        if string.count(i) > max:
            max = string.count(i)
    print max
    which is, I think, the most obvious way.
  • +
  • 0
  • -
  • Instead of iterate through your array, just keep track of the higher number by testing each time you increment a letter count.
    Log in to write an answer.