Consider a matrix of size n, consisting of lower case aplhabets. We are required to find lexicographically smallest string starting from (1,1) and ending at (n,n).From any cell (i,j) we can either go right or down.

Now it is easily solvable in O(n^3) time ans space , but it is required to solve it in O(n^2) both time and space. Any help is appreciated