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.

1. Define an array, dp of size n, where n is the length of the words, to keep track of the length of the longest increasing subsequence that ends at each position.
2. 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.
3. If it does, then update the dp value of the second position to be the maximum of its current value and the dp value of the first position plus one.
4. 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.