960. Delete Columns to Make Sorted III
Approach
LIS-style DP; dp[j] = min deletions to keep columns 0..j with column j included and all strings non-decreasing.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.
// Approach: LIS-style DP; dp[j] = min deletions to keep columns 0..j with column j included and all strings non-decreasing.
// Time: O(m²·n) Space: O(m)
public class Solution
{
public int MinDeletionSize(string[] strs)
{
int columnCount = strs[0].Length;
int[] dp = Enumerable.Repeat(1, columnCount).ToArray();
for (int currentCol = 1; currentCol < columnCount; ++currentCol)
{
for (int previousCol = 0; previousCol < currentCol; ++previousCol)
{
bool isNonDecreasing = true;
foreach (var str in strs)
{
if (str[previousCol] > str[currentCol])
{
isNonDecreasing = false;
break;
}
}
if (isNonDecreasing)
dp[currentCol] = Math.Max(dp[currentCol], dp[previousCol] + 1);
}
}
int maxIncreasingLength = dp.Max();
return columnCount - maxIncreasingLength;
}
}