Delete Columns to Make Sorted III

Delete Columns to Make Sorted III

What is this problem about?

The Delete Columns to Make Sorted III interview question is the most advanced version of the column deletion series. You need to delete columns such that each remaining string is lexicographically sorted. The twist: you want to find the maximum number of columns you can keep, or the minimum you must delete. This Delete Columns to Make Sorted III coding problem is actually a "Longest Increasing Subsequence" (LIS) problem in a 2D context.

Why is this asked in interviews?

Google asks this to see if a candidate can reduce a grid-based string problem to a classic Dynamic Programming task. It requires realizing that if we keep column i and then keep column j (j > i), then for every row, the character at row[i] must be <= the character at row[j]. It evaluates your ability to handle multi-row constraints in a single DP state.

Algorithmic pattern used

This follows the Array, String, Dynamic Programming interview pattern.

1. LIS Transformation: Let dp[i] be the maximum number of columns we can keep ending with column i.
2. Transition: dp[i] = 1 + max(dp[j]) for all j < i such that column j can precede column i.
3. Constraint: Column j can precede column i only if for every row k, grid[k][j] <= grid[k][i].
4. Result: Total_Cols - max(dp).

Example explanation

Grid: ["baaa", "abcd"]

• Col 0 ('b', 'a') vs Col 1 ('a', 'b'): Row 0 fails ('b' > 'a').
• Col 1 ('a', 'b') vs Col 2 ('a', 'c'): Both rows pass ('a' <= 'a', 'b' <= 'c'). The DP will find the longest chain of columns that satisfy the "all-row" increase condition.

Common mistakes candidates make

• Greedy approach: Trying to pick columns one by one. This fails because picking one column might prevent you from picking two others later.
• Complexity: Forgetting the O(N^2) nature of LIS, which is required here since the columns aren't necessarily adjacent.
• Inner loop logic: Failing to check all rows during the column-precedence check.

Interview preparation tip

When you need to pick a subsequence of items that satisfy a property, always think of the Longest Increasing Subsequence pattern. If the property involves multiple rows, just add an extra loop to validate the condition across all rows.