Someone asked me a question
Find the longest alphabetically increasing or equal string composed of those letters. Note that you are allowed to drop unused characters. So ghaaawxyzijbbbklccc returns aaabbbccc. Is an O(n) solution possible?
and I implemented it code [in python]
s = 'ghaaawxyzijbbbklccc' lst = [ for i in range(26)] for ch in s: ml = 0 for i in range(0,ord(ch) + 1 - ord('a')): if len(lst[i]) > len(lst[ml]): ml= i cpy = ''.join(lst[ml]) lst[ord(ch) - ord('a')] = cpy + ch ml = 0 for i in range(26): if len(lst[i]) > len(lst[ml]): ml = i print lst[ml]
and the answer is 'aaabbbccc'
I have tried this some more examples and all works! and as far as I can think the complexity of this code is O(N) let's take an example suppose I have a string 'zzzz' so the main loop will run 4 times and internal loop will run 26 times for each iteration so we can say in worst case the code will run in
O(26*N + 26) ---------^- this is the last iteration
so O(N) is acceptable?
Now questions are