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

- Is it works in O(N) my code at ideone
- If it works in O(N) then why to use DP of O(N2) code of DP
- Is it better then this code Friends code
- Limitations of this code