Delete Columns to Make Sorted III

Problem

You are given an array of n 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.

For example, if we have strs = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3}, then the final array after deletions is ["bef", "vyz"].

Suppose we chose a set of deletion indices answer such that after deletions, the final array has every string (row) in lexicographic order. (i.e., (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]), and (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]), and so on). Return the minimum possible value of answer.length.

Examples

Example 1

Input: strs = ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is strs = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. strs[0][0] <= strs[0][1] and strs[1][0] <= strs[1][1]).
Note that strs[0] > strs[1] - the array strs is not necessarily in lexicographic order.

Example 2

Input: strs = ["edcba"]
Output: 4
Explanation: If we delete less than 4 columns, the only row will not be lexicographically sorted.

Example 3

Input: strs = ["ghi","def","abc"]
Output: 0
Explanation: All rows are already lexicographically sorted.

Solution

Method 1 – Dynamic Programming (Longest Non-Decreasing Subsequence of Columns)

Intuition

The problem is to delete the minimum number of columns so that each row is lexicographically sorted. Instead of thinking about which columns to delete, we can think about which columns to keep. We want to keep the largest set of columns (in order) such that, for every row, the sequence of characters in those columns is non-decreasing. This is similar to finding the longest non-decreasing subsequence (LNDS) of columns across all rows.

Approach

1. Let m be the number of strings and n be the length of each string.
2. Use DP: dp[j] is the length of the longest valid subsequence ending at column j.
3. For each column j, check all previous columns i < j. For all rows, if strs[row][i] <= strs[row][j], then column j can follow column i in the subsequence.
4. Update dp[j] = max(dp[j], dp[i] + 1) if the above condition holds for all rows.
5. The answer is n - max(dp), i.e., the minimum columns to delete.

Code

C++

class Solution {
public:
  int minDeletionSize(vector<string>& strs) {
    int m = strs.size(), n = strs[0].size();
    vector<int> dp(n, 1);
    int ans = n - 1;
    for (int j = 0; j < n; ++j) {
      for (int i = 0; i < j; ++i) {
        bool valid = true;
        for (int k = 0; k < m; ++k) {
          if (strs[k][i] > strs[k][j]) {
            valid = false;
            break;
          }
        }
        if (valid) dp[j] = max(dp[j], dp[i] + 1);
      }
      ans = min(ans, n - dp[j]);
    }
    return ans;
  }
};

Go

func minDeletionSize(strs []string) int {
  m, n := len(strs), len(strs[0])
  dp := make([]int, n)
  for j := range dp {
    dp[j] = 1
  }
  ans := n - 1
  for j := 0; j < n; j++ {
    for i := 0; i < j; i++ {
      valid := true
      for k := 0; k < m; k++ {
        if strs[k][i] > strs[k][j] {
          valid = false
          break
        }
      }
      if valid && dp[i]+1 > dp[j] {
        dp[j] = dp[i] + 1
      }
    }
    if n-dp[j] < ans {
      ans = n - dp[j]
    }
  }
  return ans
}

Java

class Solution {
  public int minDeletionSize(String[] strs) {
    int m = strs.length, n = strs[0].length();
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int ans = n - 1;
    for (int j = 0; j < n; ++j) {
      for (int i = 0; i < j; ++i) {
        boolean valid = true;
        for (int k = 0; k < m; ++k) {
          if (strs[k].charAt(i) > strs[k].charAt(j)) {
            valid = false;
            break;
          }
        }
        if (valid) dp[j] = Math.max(dp[j], dp[i] + 1);
      }
      ans = Math.min(ans, n - dp[j]);
    }
    return ans;
  }
}

Kotlin

class Solution {
  fun minDeletionSize(strs: Array<String>): Int {
    val m = strs.size
    val n = strs[0].length
    val dp = IntArray(n) { 1 }
    var ans = n - 1
    for (j in 0 until n) {
      for (i in 0 until j) {
        var valid = true
        for (k in 0 until m) {
          if (strs[k][i] > strs[k][j]) {
            valid = false
            break
          }
        }
        if (valid) dp[j] = maxOf(dp[j], dp[i] + 1)
      }
      ans = minOf(ans, n - dp[j])
    }
    return ans
  }
}

Python

class Solution:
  def minDeletionSize(self, strs: list[str]) -> int:
    m, n = len(strs), len(strs[0])
    dp: list[int] = [1] * n
    ans: int = n - 1
    for j in range(n):
      for i in range(j):
        if all(strs[k][i] <= strs[k][j] for k in range(m)):
          dp[j] = max(dp[j], dp[i] + 1)
      ans = min(ans, n - dp[j])
    return ans

Rust

impl Solution {
  pub fn min_deletion_size(strs: Vec<String>) -> i32 {
    let m = strs.len();
    let n = strs[0].len();
    let strs: Vec<Vec<u8>> = strs.iter().map(|s| s.as_bytes().to_vec()).collect();
    let mut dp = vec![1; n];
    let mut ans = n as i32 - 1;
    for j in 0..n {
      for i in 0..j {
        let mut valid = true;
        for k in 0..m {
          if strs[k][i] > strs[k][j] {
            valid = false;
            break;
          }
        }
        if valid {
          dp[j] = dp[j].max(dp[i] + 1);
        }
      }
      ans = ans.min(n as i32 - dp[j]);
    }
    ans
  }
}

Complexity

• ⏰ Time complexity: O(n^2 * m)
• 🧺 Space complexity: O(n)