Problem Explanation

Given a list of same length strings with lower case letters. Our task is to delete some columns in the strings such that after the deletion, the letters in each column are sorted in non-decreasing order. We want to minimize the number of deletions.

For instance, if we have strings like ["zyx","wvu","tsr"], we can see that in all columns the letters are not in non decreasing order. In the first column we have 'z', 'w' and 't', in the second column 'y', 'v' and 's' and in the third column 'x', 'u' and 'r', all are in descending order. To make them in non-decreasing order, we have to delete all columns. Thus, the minimum number of deletions would be 3.

Approach

The approach is pretty simple. We iterate through each column, and in each column we compare each character with the next one. If we find that the current character is greater than the next one, then the column is not sorted, so we increment the count and break the loop to check the next column. We repeat this process until all columns are checked. The count that we get at the end is the minimum number of deletions required.

C++ Solution

1
2C++
3class Solution {
4 public:
5  int minDeletionSize(vector<string>& A) {
6    const int n = A[0].length();
7    int ans = 0;
8
9    // Iterate through each column
10    for (int j = 0; j < n; ++j) {
11      // Compare each character in the column with the next one
12      for (int i = 0; i + 1 < A.size(); ++i) {
13        // If the current character is greater than the next one
14        // the column is not sorted.
15        if (A[i][j] > A[i + 1][j]) {
16          // Increment the count and break the loop to check the next column
17          ++ans;
18          break;
19        }
20      }
21    }
22    return ans;
23  }
24};

Python Solution

1
2python 
3class Solution(object):
4    def minDeletionSize(self, A):
5        """
6        :type A: List[str]
7        :rtype: int
8        """
9        ans = 0
10        for col in zip(*A):
11            if list(col) != sorted(col):
12                ans += 1
13        return ans
14

Java Solution

1
2java
3class Solution {
4    public int minDeletionSize(String[] A) {
5        int ans = 0;
6        for (int c = 0; c < A[0].length(); ++c)
7            for (int r = 0; r < A.length - 1; ++r)
8                if (A[r].charAt(c) > A[r+1].charAt(c)) {
9                    ans++;
10                    break; 
11                }
12        return ans;
13    }
14}

JavaScript Solution

1
2javascript
3class Solution {
4    minDeletionSize(A) {
5        let deletions = 0;
6        for (let i = 0; i < A[0].length; i++) {
7            for (let j = 0; j < A.length - 1; j++) {
8                if (A[j].charAt(i) > A[j + 1].charAt(i)) {
9                    deletions++;
10                    break;
11                }
12            }
13        }
14        return deletions;
15    }
16}

C# Solution

1
2C#
3public class Solution {
4    public int MinDeletionSize(string[] A) {
5        int ans = 0;
6        for (int j = 0; j < A[0].Length; ++j) {
7            for (int i = 0; i < A.Length - 1; ++i) {
8                if (A[i][j] > A[i + 1][j]) {
9                    ++ans;
10                    break;
11                }   
12            }
13        }
14        return ans;
15    }
16}

In all above solutions, we compare each string's character with the next string's respective character, and if it is greater than the next one, increment the count of deletions otherwise check the next index. After checking all indices, return the count of deletions which is the minimum number of deletions required to make each remaining column in strings sorted.In comparison to the C++ solution, the Python solution is shorter and simpler due to Python's built-in zip function which returns an iterator of tuples, where the i-th tuple contains the i-th element from each of the argument sequences. By using 'zip(*A)', we are combining each index of the strings in A into separate tuples in a list, basically creating columns. Next, we check if the sorted list of the column is identical to the column itself. If not, it means the column is not sorted and we increment the counter 'ans' by 1.

The Java and JavaScript solutions, similarly to the C++ solution, use a nested loop to iterate over the strings and their respective characters using their indices. If a character is larger than the next one in a column, the counter is incremented and the loop responsible for checking the characters in that column is exited.

The C# solution is very similar to the Java and JavaScript solutions, as it also uses a nested for loop to iterate over the characters in a column. If an unsorted order is detected, the counter is incremented and the inner loop is exited.

In conclusion, the problem of sorting columns in a list of same length strings can be solved by using a combination of nested loops and a counter in multiple programming languages. Different languages offer different built-in functions which can make the solution more efficient and readable, but the overall logic remains the same.