PROBLEM LINK
Author: Aman Kumar Singh
Testers: Sarthak Manna, Smit Mandavia, Avijit Agarwal
Editorialist: Avijit Agarwal
DIFFICULTY
Easy - Medium
PREREQUISITES
Dynamic Programming, Breadth First Search (BFS)
PROBLEM
You are given N strings, each of length M. Each character of each string can either be a lowercase English letter or the character #. You need to choose N non-empty substrings S_i[l_i, r_i] from each string i (for all 1 \leq i \leq N) such that
- The final string is obtained by appending the substrings S_{1}[1, a_{1}], S_{2}[a_{1}, a_{2}], S_{3}[a_{2}, a_{3}], ā¦, S_{N-1}[a_{N-2}, a_{N-1}], S_{n}[a_{N-1}, M], where 1 \leq a_1 \leq a_2 \leq a_3 \leq ... \leq a_{N-1} \leq M
- None of the substrings contain any \# character.
- The final string is the lexicographically smallest possible obtainable string.
EXPLANATION
This problem is equivalent to a problem where we are given a grid A of size N*M, where each cell of the grid is either a lower case English character or the character # and we need to find the lexicographically smallest string which can be obtained by traversing from A_{1,1} to A_{N,M}, where the resultant string doesnāt contain any # and where we can move only to the right or down cells.
Let us assume the final string to be S.
Then, |S| = N+M-1
To find a character S_l of the final string S, we need to find the smallest character A_{i,j} where:
- i+j-1=l
- A_{i,j} is reachable from A_{N,M}
- A_{i,j} is not the character #
- At least one of A_{i-1,j} or A_{i,j-1} is same as S_{l-1}
We initially mark all the cells reachable from A_{N,M} in a boolean 2D array using bottom up DP starting from A_{N,M}.
Then we do Breadth First Search (BFS) from the cell A_{1,1}, layer by layer such that in the l^{\text{th}} layer we examine all the cells A_{i.j} where i+j-1=l and are reachable from
- A_{N,M}
- the previously visited cells in the (l-1)^{\text{th}} layer
We find the minimum such character in the present layer and mark all the cells which contains this minimum character as visited. We append this minimum character to the answer and repeat this process until we reach the (N+M-1)^{\text{th}} layer.
The required time complexity is \mathcal{O}(N*M)
SOLUTIONS
C++ solution can be found here.
Java solution can be found here.
Python solution can be found here.