Leetcode 960. Delete Columns to Make Sorted III
Problem Explanation
Given a list of words (strings), the task is to delete the minimum number of columns such that each remaining word is in lexicographic order.
Lexicographic order is just a fancy word for saying alphabetical order. In this context, a word (string) is considered to be in lexicographic order if every subsequent character in the word (from left to right) is the same or comes after the character before it.
This is better understood with an example. Given an array ["babca", "bbazb"], we are to delete the minimum number of columns such that each remaining words are in lexicographic order. After deleting columns 0, 1, and 4, the remaining array is ["bc", "az"]. Both these words are individually in lexicographic order (ie. "bc" and "az" are each in alphabetical order). Hence, the minimum possible number of deletions is the length of the deleted columns which is 3.
One thing to note here is that the final array as a whole doesn't have to be in lexicographic order. We just care about each single word in the array.
Approach
The algorithm uses a dynamic programming approach to solve this problem. The primary idea behind the approach is to find the longest increasing subsequence (LIS) which is a standard dynamic programming problem. The "increasing" here corresponds to "alphabetical order".
Then our answer is the original length subtracted by the length of LIS.
- Define an array,
dp
of sizen
, wheren
is the length of the words, to keep track of the length of the longest increasing subsequence that ends at each position. - Iterate through each pair of positions in the words, check if deleting all the characters in the second position would maintain the lexicographic order of the words.
- If it does, then update the
dp
value of the second position to be the maximum of its current value and thedp
value of the first position plus one. - After that, the solution would be the number of characters in the words minus the maximum value in the
dp
array.
Python Solution
1 2python 3class Solution: 4 def minDeletionSize(self, A): 5 # Length of the words 6 n = len(A[0]) 7 # DP array 8 dp = [1] * n 9 for i in range(n): 10 for j in range(i): 11 # Check if deleting all characters at position `i` would maintain lexicographic order 12 if all(row[j] <= row[i] for row in A): 13 dp[i] = max(dp[i], dp[j] + 1) 14 # Minimum number of deletions 15 return n - max(dp)
The solution iterates through each pair of positions in the words. For each pair, it checks if deleting all characters in the second position would maintain the lexicographic order of the words. If it does, then the dp
value of the second position is updated to be the maximum of its current value and the dp
value of the first position plus one. The result is then calculated by subtracting the maximum dp
value from the length of the words.
Java Solution
1 2Java 3import java.util.Arrays; 4 5class Solution { 6 public int minDeletionSize(String[] A) { 7 int n = A[0].length(); 8 int[] dp = new int[n]; 9 Arrays.fill(dp, 1); 10 for(int i = 0; i < n; ++i) 11 for(int j = 0; j < i; ++j) { 12 boolean isOrdered = true; 13 for(String a: A) { 14 if(a.charAt(j) > a.charAt(i)) { 15 isOrdered = false; 16 break; 17 } 18 } 19 if (isOrdered) { 20 dp[i] = Math.max(dp[i], dp[j] + 1); 21 } 22 } 23 int longest = Arrays.stream(dp).max().getAsInt(); 24 return n - longest; 25 } 26}
The Java solution is similar to the Python one. It iterates through the columns in pairs, checks if each word maintains lexicographic order when the character at the current position is deleted. If so, it updates the dp
array. The solution becomes the number of columns minus the length of the longest increasing subsequence.
JavaScript Solution
1 2javascript 3var minDeletionSize = function(A) { 4 const n = A[0].length; 5 const dp = new Array(n).fill(1); 6 for(let i = 1; i < n; i++) { 7 for(let j = 0; j < i; j++) { 8 if(A.every(a => a.charAt(j) <= a.charAt(i))) { 9 dp[i] = Math.max(dp[i], dp[j] + 1); 10 } 11 } 12 } 13 return n - Math.max(...dp); 14};
Similarly, in JavaScript, we initialize an array dp
to track the length of the longest increasing subsequence that ends at each position. We then iterate over the array two loops, checking the lexicographic order. If it holds, we update the dp
array accordingly. Finally, the minimum deletion size is calculated as the total size n
minus the maximum in the dp
array.
C++ Solution
1
2cpp
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 int minDeletionSize(vector<string>& A) {
9 int n = A[0].size();
10 vector<int> dp(n, 1);
11 for (int i = 0; i < n; i++) {
12 for (int j = 0; j < i; j++) {
13 if (is_in_order(A, j, i)) {
14 dp[i] = max(dp[i], dp[j] + 1);
15 }
16 }
17 }
18 return n - *max_element(dp.begin(), dp.end());
19 }
20
21private:
22 bool is_in_order(vector<string>& A, int i, int j) {
23 for (string& s : A) {
24 if (s[i] > s[j]) {
25 return false;
26 }
27 }
28 return true;
29 }
30};
The C++ solution is similar to the Python, Java, and JavaScript solutions. It also uses a dp
array to keep track of the longest increasing subsequence at each position. Additionally, it uses a helper function to simplify checking for lexicographic order in given ranges.
C# Solution
1 2cs 3using System; 4using System.Linq; 5 6public class Solution { 7 public int MinDeletionSize(string[] A) { 8 int n = A[0].Length; 9 int[] dp = new int[n]; 10 Array.Fill(dp, 1); 11 for (int i = 0; i < n; ++i) 12 for (int j = 0; j < i; ++j) 13 if (IsInOrder(A, j, i)) 14 dp[i] = Math.Max(dp[i], dp[j] + 1); 15 return n - dp.Max(); 16 } 17 18 private bool IsInOrder(string[] A, int j, int i) { 19 for (int k = 0; k < A.Length; k++) 20 if (A[k][j] > A[k][i]) 21 return false; 22 return true; 23 } 24}
The C# solution is very similar to the previous ones. A dp
array is used to track the longest increasing subsequence ending at each index. The IsInOrder
helper function is used to simplify the lexicographic order checks. The result is calculated as the total size n
minus the maximum value in the dp
array.## Go Solution
1 2go 3package main 4 5import ( 6 "strings" 7) 8 9func minDeletionSize(A []string) int { 10 n := len(A[0]) 11 dp := make([]int, n) 12 fill(dp, 1) 13 14 for i := 0; i < n; i++ { 15 for j := 0; j < i; j++ { 16 if isOrdered(A, j, i) { 17 dp[i] = max(dp[i], dp[j]+1) 18 } 19 } 20 } 21 22 return n - maxInSlice(dp) 23} 24 25func fill(arr []int, val int) { 26 for i := range arr { 27 arr[i] = val 28 } 29} 30 31func isOrdered(A []string, i int, j int) bool { 32 for _, s := range A { 33 if s[i] > s[j] { 34 return false 35 } 36 } 37 return true 38} 39 40func max(x, y int) int { 41 if x > y { 42 return x 43 } 44 return y 45} 46 47func maxInSlice(arr []int) int { 48 maxVal := arr[0] 49 for _, v := range arr { 50 if v > maxVal { 51 maxVal = v 52 } 53 } 54 return maxVal 55}
This Go solution follows the same approach as the Python, Java, JavaScript, C++, and C# solutions. It uses a slice, dp
, to keep track of the longest increasing subsequence that ends at each position. The helper function, isOrdered
, is used to check if the words are in lexicographical order when deleting the character at the current position, and if it does, the dp
value at that position is updated. Finally, the solution calculates the minimum number of deletions by subtracting the maximum value in the dp
slice from the length of the words.
For this Go solution, we had to create helper function fill
to fill the dp
slice with 1, as Go does not have a built-in function like Arrays.fill
of Java or Array.fill
of C#. Similarly, we had to create helper functions max
and maxInSlice
to find the maximum in a pair of integers and in an integer slice, since Go does not have built-in functions like Math.max
/Math.Max
or Arrays.stream(dp).max().getAsInt()
of Java, Math.max
of JavaScript, *max_element
of C++, or dp.Max()
of C#.
Rust Solution
1 2rust 3impl Solution { 4 pub fn min_deletion_size(A: Vec<String>) -> i32 { 5 let n = A[0].len(); 6 let mut dp = vec![1; n]; 7 for i in 0..n { 8 for j in 0..i { 9 if Self::is_ordered(&A, j, i) { 10 dp[i] = dp[i].max(dp[j]+1); 11 } 12 } 13 } 14 return (n as i32) - *dp.iter().max().unwrap(); 15 } 16 17 fn is_ordered(A: &Vec<String>, i: usize, j: usize) -> bool { 18 for s in A { 19 if s.as_bytes()[i] > s.as_bytes()[j] { 20 return false; 21 } 22 } 23 return true; 24 } 25}
The Rust solution shares the same approach with the others. A vector, dp
, tracks the longest increasing subsequence that ends at each position. For the helper function is_ordered
, we utilize Rust's as_bytes
method to retrieve a byte slice of the string slice for comparison. We calculate the minimum deletion size by subtracting the value of the largest integer in the dp
vector from the total size n
. Here, we used the built-in method vec![1; n]
which creates a Vec dp
with n
elements, all being 1
. Also, the iter().max().unwrap()
gives maximum in the dp
.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.