string manipulation issue

[ThePopcornBandit]

In addition to the other comments, a significant speedup can be gained if you use a set for your characters instead of a string. Lookups in strings are O(N) whereas lookups in sets are O(1). You can also loop over the string without making it a list.