Question

Google | OA Coding Questions and Solutions | Set - 20 | 2022

Answer 1

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

Answer 2

Images of ques