fork(1) download
copy 
  1. s = 'ghaaawxyzijbbbklccc'
  2. #s = 'deepanshu'     #My name :D
  3. #s = 'somerandomstring'
  4. lst = [1 for i in range(0,len(s))]
  5. rng = [i for i in range(0,len(s))]
  6. stack = []
  7. res = ''
  8. for i in range(1,len(s)):
  9.     for j in range(0,i):
  10.         if s[j] <= s[i]:
  11.             #rng[i] = j   #Look at my code it works in O(N2) :(
  12.             temp = lst[i]
  13. 	    lst[i] = max(1 + lst[j],lst[i])
  14. 	    if lst[i] != temp:
  15. 		rng[i] = j
  16.  
  17.  
  18. #print '[' + s[0] + ',',              #Debug it :-/ I know you nailed it ;)
  19. #for i in range(1,len(s) - 1):        #Debug it :-/ I know you nailed it ;)
  20. #    print s[i] + ',',                #Debug it :-/ I know you nailed it ;)
  21. #print s[i + 1] + ']'                 #Debug it :-/ I know you nailed it ;)
  22. #print lst                            #Debug it :-/ I know you nailed it ;)
  23. #print rng                            #Debug it :-/ I know you nailed it ;)
  24.  
  25.  
  26. m = lst[0]
  27. idx = 0
  28. for i in range(1,len(s)):
  29.     if m < lst[i]:
  30.         m = lst[i]
  31.         idx = i
  32.  
  33. stack.append(idx)
  34. while idx != rng[idx]:
  35.     stack.append(rng[idx])
  36.     idx = rng[idx]
  37.  
  38. for i in stack:
  39.     res += s[i]
  40.  
  41. res = ''.join(reversed(res))
  42. print res
Success #stdin #stdout 0.01s 7736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
aaabbbccc
https://ideone.com/LrS1iP
language:
Python (cpython 2.7.16)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!