s = 'ghaaawxyzijbbbklccc'
#s = 'deepanshu' #My name :D
#s = 'somerandomstring'
lst = [1 for i in range(0,len(s))]
rng = [i for i in range(0,len(s))]
stack = []
res = ''
for i in range(1,len(s)):
for j in range(0,i):
if s[j] <= s[i]:
#rng[i] = j #Look at my code it works in O(N2) :(
temp = lst[i]
lst[i] = max(1 + lst[j],lst[i])
if lst[i] != temp:
rng[i] = j
#print '[' + s[0] + ',', #Debug it :-/ I know you nailed it ;)
#for i in range(1,len(s) - 1): #Debug it :-/ I know you nailed it ;)
# print s[i] + ',', #Debug it :-/ I know you nailed it ;)
#print s[i + 1] + ']' #Debug it :-/ I know you nailed it ;)
#print lst #Debug it :-/ I know you nailed it ;)
#print rng #Debug it :-/ I know you nailed it ;)
m = lst[0]
idx = 0
for i in range(1,len(s)):
if m < lst[i]:
m = lst[i]
idx = i
stack.append(idx)
while idx != rng[idx]:
stack.append(rng[idx])
idx = rng[idx]
for i in stack:
res += s[i]
res = ''.join(reversed(res))
print res
cyA9ICdnaGFhYXd4eXppamJiYmtsY2NjJwojcyA9ICdkZWVwYW5zaHUnICAgICAjTXkgbmFtZSA6RAojcyA9ICdzb21lcmFuZG9tc3RyaW5nJwpsc3QgPSBbMSBmb3IgaSBpbiByYW5nZSgwLGxlbihzKSldCnJuZyA9IFtpIGZvciBpIGluIHJhbmdlKDAsbGVuKHMpKV0Kc3RhY2sgPSBbXQpyZXMgPSAnJwpmb3IgaSBpbiByYW5nZSgxLGxlbihzKSk6CiAgICBmb3IgaiBpbiByYW5nZSgwLGkpOgogICAgICAgIGlmIHNbal0gPD0gc1tpXToKICAgICAgICAgICAgI3JuZ1tpXSA9IGogICAjTG9vayBhdCBteSBjb2RlIGl0IHdvcmtzIGluIE8oTjIpIDooCiAgICAgICAgICAgIHRlbXAgPSBsc3RbaV0KCSAgICBsc3RbaV0gPSBtYXgoMSArIGxzdFtqXSxsc3RbaV0pCgkgICAgaWYgbHN0W2ldICE9IHRlbXA6CgkJcm5nW2ldID0gagoKCiNwcmludCAnWycgKyBzWzBdICsgJywnLCAgICAgICAgICAgICAgI0RlYnVnIGl0IDotLyBJIGtub3cgeW91IG5haWxlZCBpdCA7KQojZm9yIGkgaW4gcmFuZ2UoMSxsZW4ocykgLSAxKTogICAgICAgICNEZWJ1ZyBpdCA6LS8gSSBrbm93IHlvdSBuYWlsZWQgaXQgOykKIyAgICBwcmludCBzW2ldICsgJywnLCAgICAgICAgICAgICAgICAjRGVidWcgaXQgOi0vIEkga25vdyB5b3UgbmFpbGVkIGl0IDspCiNwcmludCBzW2kgKyAxXSArICddJyAgICAgICAgICAgICAgICAgI0RlYnVnIGl0IDotLyBJIGtub3cgeW91IG5haWxlZCBpdCA7KQojcHJpbnQgbHN0ICAgICAgICAgICAgICAgICAgICAgICAgICAgICNEZWJ1ZyBpdCA6LS8gSSBrbm93IHlvdSBuYWlsZWQgaXQgOykKI3ByaW50IHJuZyAgICAgICAgICAgICAgICAgICAgICAgICAgICAjRGVidWcgaXQgOi0vIEkga25vdyB5b3UgbmFpbGVkIGl0IDspCgoKbSA9IGxzdFswXQppZHggPSAwCmZvciBpIGluIHJhbmdlKDEsbGVuKHMpKToKICAgIGlmIG0gPCBsc3RbaV06CiAgICAgICAgbSA9IGxzdFtpXQogICAgICAgIGlkeCA9IGkKCnN0YWNrLmFwcGVuZChpZHgpCndoaWxlIGlkeCAhPSBybmdbaWR4XToKICAgIHN0YWNrLmFwcGVuZChybmdbaWR4XSkKICAgIGlkeCA9IHJuZ1tpZHhdCgpmb3IgaSBpbiBzdGFjazoKICAgIHJlcyArPSBzW2ldCgpyZXMgPSAnJy5qb2luKHJldmVyc2VkKHJlcykpCnByaW50IHJlcw==