Cut Columns to Sort Every Row

Hard

You get a list rows of strings of equal length. Picture them as a grid of letters: each string is a row and each character position is a column. You may cut out any columns; a cut position disappears from every string at once. Afterwards **each** string on its own must be in alphabetical order (no letter is smaller than the one before it). How the strings compare to each other does not matter. Return the smallest number of columns you have to cut.

Example 1

rows=["cadb", "bcxd"] → 2

Keep columns 1 and 3: the rows become ab and cd, both in order. That cuts 2 columns, and no set of three columns works.

Example 2

rows=["pqr", "abz", "mmm"] → 0

Every row is already in alphabetical order, so nothing needs cutting. It does not matter that the rows themselves are out of order.

Example 3

rows=["zyxw"] → 3

The letters strictly decrease, so only one column can stay: cut 3.

Constraints

1 ≤ len(rows) ≤ 100
1 ≤ len(rows[i]) ≤ 100, all strings have the same length
Strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array String Dynamic Programming

Similar problems

Every Way to Space the Words Hard Words Built From Shorter Words Hard Numbers From Working Keys Hard Assembling Fragments Hard Best Word Set From Tiles Hard

Input

rows=["cadb", "bcxd"]

Expected

Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.