We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Delete Columns to Make Sorted III

Number: 1000

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an array of n strings of equal length, we are allowed to delete any set of columns. After deletion, each string (i.e., each row) must have its remaining characters in non-decreasing (i.e., lexicographic) order. The goal is to determine the minimum number of columns that need to be deleted so that every row is individually sorted.

Key Insights

  • The problem can be reinterpreted as selecting the largest sequence of columns to keep such that, for every row, the characters in the selected columns are in non-decreasing order.
  • This is analogous to finding the Longest Increasing Subsequence (LIS) where each "element" (column) must be compatible with previously chosen columns across all rows.
  • We use dynamic programming: for each column, consider previous columns that can be appended while maintaining the sorted property for every row.
  • Finally, the answer is the total number of columns minus the length of this maximum valid subsequence (i.e., columns to keep).

Space and Time Complexity

Time Complexity: O(m^2 * n)

  • m is the number of columns and n is the number of rows; in the worst-case, we compare each pair of columns across all rows. Space Complexity: O(m)
  • We maintain a DP array of size m.

Solution

The approach is to use dynamic programming to compute the maximum number of columns we can keep such that every row is non-decreasing in the kept columns. For each column j (from 0 to m - 1), we iterate over every previous column i (from 0 to j - 1) and check if, for every row, the character in column i is less than or equal to that in column j. If the condition holds, column j can extend the valid sequence ending at column i. We update dp[j] accordingly. The final answer is obtained by subtracting the length of the longest valid subsequence from the total number of columns.

This method leverages a simple comparison between columns over all rows, ensuring that the lexicographic condition (non-decreasing order) holds for every string independently.

Code Solutions

# Python Solution
# The function takes a list of strings "strs" and returns the minimum number of columns to delete.
def minDeletionSize(strs):
    if not strs: 
        return 0
    m = len(strs[0])
    n = len(strs)
    
    # Initialize dp array where dp[j] is the length of the longest valid sequence ending at column j.
    dp = [1] * m
    
    # Check every pair of columns (i, j) where i < j.
    for j in range(m):
        for i in range(j):
            valid = True
            # Check for all rows if column i <= column j.
            for row in range(n):
                if strs[row][i] > strs[row][j]:
                    valid = False
                    break
            if valid:
                dp[j] = max(dp[j], dp[i] + 1)
    
    max_keep = max(dp)
    # The answer is the total columns minus the maximum sequence length.
    return m - max_keep

# Example usage:
print(minDeletionSize(["babca", "bbazb"]))  # Expected output: 3
← Back to All Questions