Approach 1: Dynamic Programming
Intuition and Algorithm
This is a tricky problem that is hard to build an intuition about.
First, lets try to find the number of columns to keep, instead of the number to delete. At the end, we can subtract to find the desired answer.
Now, let's say we must keep the first column
C. The next column
D we keep must have all rows lexicographically sorted (ie.
C[i] <= D[i]), and we can say that we have deleted all columns between
Now, we can use dynamic programming to solve the problem in this manner. Let
dp[k] be the number of columns that are kept in answering the question for input
[row[k:] for row in A]. The above gives a simple recursion for
Time Complexity: , where is the length of
A, and is the length of each word in
Space Complexity: .
Analysis written by: @awice.