Problem Breakdown
We are given an array of n strings (strs) where every string has the same length. We need to remove a minimum number of columns (character indices) such that the resulting rows form a lexicographically non-decreasing sequence ().
Key Constraints & Inputs:
- Input: List of strings
strs, all same length. , . - Output: Integer representing minimum deletions.
- Implicit Constraint: Lexicographical comparison stops at the first differing character. If prefixes are identical up to a point, subsequent characters determine order for that specific pair of rows.
Tricky Edge Cases:
- Already Sorted: No columns need deletion (Output: 0).
- Single Row (): Always sorted regardless of content (Loop over pairs won’t execute).
- Identical Rows: If initially, they remain tied until a difference is found or the end.
- Strictly Decreasing Columns: Every column must be deleted if it violates order for any currently “tied” pair of rows.
Intuition
A brute-force approach would try all subsets of columns to delete, which is exponential and infeasible (). We need a greedy strategy that processes column by column from left to right.
Key Insight: Lexicographical order between two adjacent rows depends on the first column where they differ. If row and row have been identical in all kept columns so far, we are currently “tied” for this pair.
- Tie State: We track which pairs are still effectively equal based on previous kept columns using a boolean array
is_less. Initially, all False (all tied). - Decision Rule: For the current column:
- If any currently “tied” pair has , this column breaks the sorted order for that specific pair. Since we cannot fix a violation in future columns (lexicographical comparison is determined by earlier differences), we must delete this entire column to avoid an invalid state.
- If and they were tied, the order for that pair is now established ( comes before ). We mark them as resolved (
is_less= True) so we stop checking this specific pair in future columns. - If equal, they remain tied (False), requiring further checks on subsequent columns.
Approach
We iterate through each column index from left to right ( to ). We maintain a state array is_less of size , initialized to False. This tracks which adjacent rows have already established strict order based on previously kept columns.
For every column:
- Check for Violations: Iterate through all pairs where
!is_less[i]. If we find any pair where , this column is invalid and must be deleted (ans += 1). We skip updating the state because the column doesn’t exist in the final array. - Update State: If no violations are found (column kept), iterate through all pairs again where
!is_less[i]. If , mark this pair as resolved (is_less[i] = True). Pairs with equal characters remain tied.
Finally, return the total count of deleted columns.
Complexity Analysis
- Time Complexity: , where is number of strings and is string length. We iterate through each column once () and for each column scan all adjacent pairs (). Given constraints , this is roughly operations.
- Space Complexity: to store the
is_lessboolean array.
Solution
class Solution:
def minDeletionSize(self, strs):
n = len(strs)
if n <= 1:
return 0
m = len(strs[0])
ans = 0
# Tracks whether pair (i, i+1) is strictly ordered based on kept columns.
# False means they are still tied/equal from previous kept columns.
is_less = [False] * (n - 1)
for col in range(m):
delete_col = False
# Check if any currently tied pair violates order at this column
for i in range(n - 1):
if not is_less[i]:
if strs[i][col] > strs[i + 1][col]:
delete_col = True
break
if delete_col:
ans += 1
else:
# If column kept, update state for pairs that become strictly ordered
for i in range(n - 1):
if not is_less[i] and strs[i][col] < strs[i + 1][col]:
is_less[i] = True
return ans
Edge Cases Handled
- Single String (): The loop
range(n-1)becomes empty, returning 0 immediately. Correct as a single string is always sorted. - Already Sorted: No column triggers the deletion condition; state updates correctly but no deletions occur. Returns 0.
- All Tied Rows (e.g., [“a”, “b”] vs [“c”, “d”]): Logic handles transitions from tied to resolved states based on character comparison.
- Violation in First Column: If for any pair,
delete_colbecomes True immediately, incrementing count and skipping state updates (rows remain conceptually equal).