Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
1,252 views
in Online Assessments by Expert (46,090 points) | 1,252 views

2 Answers

0 like 0 dislike

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

by Expert (111,530 points)
0 like 0 dislike

Images of ques

image

 

by Expert (46,090 points)