Delete Columns to Make Sorted III - Practice Coding Problems

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.

Input & Output

Example 1 — Basic Case

$ Input: strs = ["cab","daf","ghi"]

› Output: 1

💡 Note: We can delete column 0. After deletion: ["ab","af","hi"]. Each string is now lexicographically sorted: a≤b, a≤f, h≤i.

Example 2 — No Deletions Needed

$ Input: strs = ["abc","def","ghi"]

› Output: 0

💡 Note: All strings are already lexicographically sorted. No columns need to be deleted.

Example 3 — Multiple Deletions

$ Input: strs = ["zyx","wvu","tsr"]

› Output: 2

💡 Note: Keep only the last column. After deleting columns 0 and 1: ["x","u","r"]. Each string has only one character, so they're sorted.

Constraints

n == strs.length
1 ≤ n ≤ 100
1 ≤ strs[i].length ≤ 100
strs[i] consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array of strings with same length, need all rows sorted

Column Selection

Find which columns to keep for maintaining order

Minimum Deletions

Calculate minimum columns to delete

Key Takeaway

🎯 Key Insight: Find the longest subsequence of columns that keeps all strings sorted, then delete the rest

Asked in

G Google 25 f Facebook 18

The key insight is to find the longest subsequence of columns that keeps all strings lexicographically sorted. We can use dynamic programming to build this subsequence efficiently. The answer is total columns minus the length of this longest valid subsequence. Time: O(m² × n), Space: O(m).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^m × n × m)	O(m)	Try every possible combination of columns to delete
Dynamic Programming - Longest Increasing Subsequence	O(m² × n)	O(m)	Find longest subsequence of columns that keeps all strings sorted

Brute Force - Try All Combinations — Algorithm Steps

Generate all 2^m possible column deletion combinations
For each combination, check if remaining columns keep strings sorted
Track minimum deletions needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Create all 2^m possible deletion sets

Validate Each

Check if remaining columns keep strings sorted

Find Minimum

Return smallest valid deletion count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isSortedAfterDeletion(char strs[][101], int n, int mask, int m) {
    for (int i = 0; i < n; i++) {
        char prevChar = 0;
        for (int j = 0; j < m; j++) {
            if (!(mask & (1 << j))) {
                if (strs[i][j] < prevChar) return 0;
                prevChar = strs[i][j];
            }
        }
    }
    return 1;
}

int solution(char strs[][101], int n, int m) {
    if (n == 0 || m == 0) return 0;
    
    int minDeletions = m;
    
    for (int mask = 0; mask < (1 << m); mask++) {
        if (isSortedAfterDeletion(strs, n, mask, m)) {
            int deletions = __builtin_popcount(mask);
            if (deletions < minDeletions) {
                minDeletions = deletions;
            }
        }
    }
    
    return minDeletions;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char strs[100][101];
    int n = 0;
    
    char* token = strtok(line, "[],\"\n");
    while (token != NULL && strlen(token) > 0) {
        if (strlen(token) > 1) {
            strcpy(strs[n], token);
            n++;
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    int m = (n > 0) ? strlen(strs[0]) : 0;
    printf("%d\n", solution(strs, n, m));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^m × n × m)

2^m combinations, each requiring O(n×m) validation

✓ Linear Growth

Space Complexity

O(m)

Recursion stack depth and temporary storage

✓ Linear Space

12.0K Views

Medium Frequency

~35 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler