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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Delete Columns to Make Sorted III

Difficulty: Hard

Problem Description

You are given an array of strings strs, all of the same length. We may choose any deletion indices, and we delete all the characters in those indices for each string. The goal is to find the minimum possible value of deletion indices such that every string in the resulting array is in lexicographic order.

Key Insights

  • The problem can be reduced to finding the longest increasing subsequence of columns based on the lexicographic order of characters.
  • Each column's characters can be treated as a tuple which can be compared to other column tuples.
  • The minimum number of deletions is equal to the total number of columns minus the length of the longest increasing subsequence of the column tuples.

Space and Time Complexity

Time Complexity: O(n * m^2) where n is the number of strings and m is the length of each string (columns). Space Complexity: O(m) for storing the tuples of columns.

Solution

The solution involves creating a list of tuples where each tuple represents characters from each string at a specific column. We then apply a dynamic programming approach to find the longest increasing subsequence among these tuples. The difference between the total number of columns and the length of this subsequence gives us the minimum deletions needed.

Code Solutions

def minDeletionSize(strs):
    if not strs:
        return 0
    
    num_rows = len(strs)
    num_cols = len(strs[0])
    
    # Create a list to store the columns as tuples
    columns = [tuple(strs[i][j] for i in range(num_rows)) for j in range(num_cols)]
    
    # DP array to find the length of the longest increasing subsequence
    dp = [1] * num_cols
    
    for i in range(num_cols):
        for j in range(i):
            if columns[j] <= columns[i]:  # Compare tuples
                dp[i] = max(dp[i], dp[j] + 1)
    
    # The number of columns to delete
    return num_cols - max(dp)
← Back to All Questions