4 ms·

Can you do it in linear time in the length of the input?

• drdo 15y ago
  It's not hard to prove that that's impossible
  • ithayer 15y ago
    :) I meant linear, but I'd review a proof :)
  • amalcon 15y ago
    It's possible if RAM isn't a constraint, using a bitset of all possible five-letter strings. The bitset would take up 4G of RAM (128G for extended ASCII, more for unicode). In practice, that would actually be slower on this input, because of the cost of initializing the bitset. But that is not dependent on the input, so computational complexity is unaffected. edit: Removed description. Yes, you're right, you can't even look at the whole input in constant time.
    • drdo 15y ago
      Didn't understand what you meant, care to elaborate?
    • drdo 15y ago
      This is a misunderstanding, you must have answered to my reply after ithayer edited his comment, the initial comment said "constant time".
• kilburn 15y ago
  Find an actual (amortized) linear time implementation for this question in the following gist: https://gist.github.com/1026638 https://gist.github.com/1026638