TC: O(n^2)
Extra space: O(n^2)
def fun(s):
n=len(s)
max_ij=[[-1]*n for i in range(n)] #gives the 0 based index of the max character in s[i:j+1]
for i in range(n):
for j in range(i,n):
if i==j:
max_ij[i][j]=i # initialize
else:
if s[j]>s[max_ij[i][j-1]]:
max_ij[i][j]=j # update if new max character found
else:
max_ij[i][j]=max_ij[i][j-1]
ans=[]
for length in range(1,n+1):
curr_ans=[]
start=0
for left in reversed(range(1,length+1)):
max_index=max_ij[start][n-left] # get the max character in s[start:n-left+1] in O(1) because we still need left characters so can't utilize last left characters
curr_ans.append(s[max_index])
start=max_index+1
ans.append("".join(curr_ans))
return ans
s="hrwaw"
ans=fun(s)
print(ans)
Space complexity can be further reduced by using Range Query and printing output and for each length