algoadvance

You are given an array of n strings strs, all of the same length.

The strings can be arranged such that there is one string under each column. If you do this, you will have a grid of characters.

You need to delete columns that are not sorted lexicographically, and return the number of columns that you should delete.

Example:

Input: ["cba", "daf", "ghi"]
Output: 1
Explanation: The grid looks like this:
  c d g
  b a h
  a f i
Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete 1 column.

Clarifying Questions

1. Are the strings guaranteed to have the same length? Yes, the problem guarantees that all strings in the input array will have the same length.

2. What are the constraints on the lengths of the strings and the number of strings? Typically, for such problems, there might be constraints like each string has a fixed length (e.g., less than 1000), and the total number of strings is also limited (e.g., less than 1000). These constraints ensure our solution can run efficiently.

3. Can the input list of strings be empty or contain empty strings? We assume the input list will contain non-empty strings and the list itself will not be empty based on standard problem constraints unless explicitly stated otherwise.

Code

def minDeletionSize(strs):
    # Number of columns to delete
    delete_count = 0
    # Length of strings (number of columns)
    num_columns = len(strs[0])
    # Number of strings (number of rows)
    num_rows = len(strs)
    
    for col in range(num_columns):
        for row in range(1, num_rows):
            if strs[row][col] < strs[row - 1][col]:
                delete_count += 1
                break
    return delete_count

# Example usage:
strs = ["cba", "daf", "ghi"]
print(minDeletionSize(strs))  # Output: 1

Strategy

1. Initialization:
   • Initialize a counter delete_count to zero. This will count the number of columns that need to be deleted.
   • Determine the number of columns by checking the length of any string in the array.
   • Determine the number of rows by checking the length of the input array.
2. Column Check:
   • Iterate through each column index from 0 to the total number of columns.
   • For each column, iterate through the rows from the second row to the last row.
   • For each cell, compare the current cell’s character with the character in the same column of the previous row.
   • If the current cell character is less than the previous cell character in the same column, increment the delete_count by 1 and break out of the inner loop to move to the next column.
3. Result:
   • Return the count of columns that need to be deleted.

Time Complexity

• Time Complexity: The solution involves a nested loop where we iterate through each column and each row within that column. Hence, the time complexity is (O(n \times m)), where (n) is the number of rows and (m) is the number of columns (or the length of each string).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?