AMAZON_HACKON Coding Question – Solved

You are given an NxN matrix 'mat' where each cell contains one of the two characters 'a' or 'z'. A man stands at the bottom-right corner of the matrix (mat[N-1][N-1]) and wants to reach the top-left corner of the matrix (mat[0][0]). The man can only move up or left at each step. Your task is to find the lexicographically smallest string that can be formed by following any valid path from mat[N-1][N-1] to mat[0][0]. Additionally, determine the number of distinct paths that yield this lexicographically smallest string. Input Format: First line of input takes integer 'N' denoting the dimensions of the matrix 'mat'. The next 'N' lines take 'N' space-separated characters either 'a' or 'z' representing the values in the matrix 'mat'. Output Format: The first line of output shows the lexicographically smallest string that can be formed by any valid path from mat[N-1][N-1] to mat[0][0]. The last line of the output shows the number of distinct paths that yield this lexicographically smallest string. Constraints: 2 <= N <= 40 Sample Testcase 1 Input: 3 z a z a a a z z z Output: zaaaz 2 Explanation: Starting from mat[2][2] = 'z', the next move can either be up or left. If we move up to mat[1][2] = 'a', then move left to mat[1][1] = 'a', then move either up or left to mat[1][0] or mat[0][1] = 'a', and finally move up to mat[0][0] = 'z', the path forms the string "zaaaz", the lexicographically smallest string. Therefore, the number of possible paths = 2. Sample Testcase 2 Input: 4 z z a z z z a a z z a z a a a a Output: aaaaazz 1 Explanation: Starting from mat[3][3] = 'a', the next move can either be up or left. Moving up to mat[2][3] = 'a', then up to mat[1][3] = 'a', then up to mat[0][3] = 'a', then left to mat[0][2] = 'a', then left to mat[0][1] = 'z', and finally left to mat[0][0] = 'z', the path forms the string "aaaaazz", which is the lexicographically smallest string. Therefore, the number of possible paths that form the string is 1.