We are given an array A of N lowercase letter strings, all of the same length.
Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.
For example, if we have an array A = ["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 D such that after deletions, the final array has its elements in lexicographic order (A[0] <= A[1] <= A[2] ... <= A[A.length - 1]).
Return the minimum possible value of D.length.
 







Example 1:
Input: ["ca","bb","ac"]
Output: 1
Explanation: 
After deleting the first column, A = ["a", "b", "c"].
Now A is in lexicographic order (ie. A[0] <= A[1] <= A[2]).
We require at least 1 deletion since initially A was not in lexicographic order, so the answer is 1.


Example 2:
Input: ["xc","yb","za"]
Output: 0
Explanation: 
A is already in lexicographic order, so we don't need to delete anything.
Note that the rows of A are not necessarily in lexicographic order:
ie. it is NOT necessarily true that (A[0][0] <= A[0][1] <= ...)


Example 3:
Input: ["zyx","wvu","tsr"]
Output: 3
Explanation: 
We have to delete every column.

 


Note:

1 <= A.length <= 100
1 <= A[i].length <= 100

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Greedy algorithms

Starter code: class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        

Solutions:
class Solution:

	def minDeletionSize(self, A: List[str]) -> int:

		def isSorted(arr, i, j):
			return all((arr[k] <= arr[k + 1] for k in range(i, j)))
		ans = 0
		ranges = [[0, len(A) - 1]]
		for col in zip(*A):
			if not ranges:
				break
			if all((isSorted(col, i, j) for (i, j) in ranges)):
				tmp = []
				for (i, j) in ranges:
					start = i
					for k in range(i, j + 1):
						if col[k] != col[start]:
							if k - start > 1:
								tmp.append([start, k - 1])
							start = k
					if j + 1 - start > 1:
						tmp.append([start, j])
					start = k
				ranges[:] = tmp
			else:
				ans += 1
		return ans


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		D = set()
		while True:
			changes = False
			last_str = ''
			for (i, ch) in enumerate(A[0]):
				if i not in D:
					last_str += ch
			for x in A[1:]:
				this_str = ''
				this_idx = []
				for (i, ch) in enumerate(x):
					if i not in D:
						this_str += ch
						this_idx.append(i)
				while this_str < last_str:
					for i in range(len(this_str)):
						if this_str[i] < last_str[i]:
							D.add(this_idx[i])
							this_idx = this_idx[:i] + this_idx[i + 1:]
							this_str = this_str[:i] + this_str[i + 1:]
							last_str = last_str[:i] + last_str[i + 1:]
							changes = True
							break
				last_str = this_str
			if not changes:
				break
		return len(D)


class Solution:

	def checkLexOrder(self, A: List[str]):
		if A == sorted(A):
			return True
		else:
			return False

	def findDelIndices(self, A: List[str]):
		iter_ = len(A[0])
		to_be_del = []
		temp = [''] * len(A)
		for i in range(iter_):
			if self.checkLexOrder([x[i] for x in A]) == True:
				temp = [temp[j] + A[j][i] for j in range(len(A))]
			else:
				temp_ = [temp[j] + A[j][i] for j in range(len(A))]
				if self.checkLexOrder(temp_) == True:
					temp = [temp[j] + A[j][i] for j in range(len(A))]
				else:
					to_be_del.append(i)
		return len(to_be_del)

	def minDeletionSize(self, A: List[str]) -> int:
		if self.checkLexOrder(A):
			return 0
		else:
			return self.findDelIndices(A)


class Solution:

	def isArrSorted(self, a) -> tuple((bool, bool)):
		is_exp_sorted = True
		is_eq_sorted = True
		for (i, l) in enumerate(a):
			if i == len(a) - 1:
				break
			if not l < a[i + 1]:
				is_exp_sorted = False
			if not l <= a[i + 1]:
				is_eq_sorted = False
		return (is_exp_sorted, is_eq_sorted)

	def minDeletionSize(self, A: List[str]) -> int:
		deletion_count = 0
		built_A = [''] * len(A)
		for i in range(0, len(A[0])):
			letters_at_i = [s[i] for s in A]
			(is_exp_sorted, is_eq_sorted) = self.isArrSorted(letters_at_i)
			if is_exp_sorted:
				break
			test_A = [built_A[oi] + o[i] for (oi, o) in enumerate(A)]
			if list(sorted(test_A)) == test_A:
				built_A = test_A
				continue
			else:
				deletion_count += 1
		return deletion_count


class Solution:

	def minDeletionSize(self, words: List[str]) -> int:
		n = len(words)
		if n == 0:
			return 0
		w = len(words[0])
		intervals = [[0, n]]
		del_cols = 0
		for col in range(w):
			next_intervals = []
			del_this_col = 0
			for (start, end) in intervals:
				cprev = words[start][col]
				iprev = start
				for i in range(start + 1, end):
					c = words[i][col]
					if c > cprev:
						next_intervals.append([iprev, i])
						cprev = c
						iprev = i
					elif c < cprev:
						del_this_col = 1
						del_cols += 1
						break
					pass
				if del_this_col:
					break
				next_intervals.append([iprev, end])
				pass
			if not del_this_col:
				intervals = next_intervals
			pass
		return del_cols


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		L = len(A)
		N = len(A[0])
		sort_groups = [[i for i in range(L)]]
		count = 0
		for i in range(N):
			new_groups = []
			in_order = True
			for group in sort_groups:
				new_group = []
				curr_ord = 0
				for g_idx in group:
					char = A[g_idx][i]
					if ord(char) > curr_ord:
						if curr_ord != 0:
							new_groups.append(new_group)
						new_group = [g_idx]
						curr_ord = ord(char)
					elif ord(char) == curr_ord:
						new_group.append(g_idx)
					else:
						in_order = False
						break
				if not in_order:
					break
				if new_group != []:
					new_groups.append(new_group)
			if in_order:
				sort_groups = new_groups
			else:
				count += 1
		return count


class Solution:

	def minDeletionSize(self, A):
		(m, n) = (len(A), len(A[0]))
		first = [False] * m
		res = 0
		for j in range(n):
			for i in range(1, m):
				if not first[i] and A[i][j] < A[i - 1][j]:
					res += 1
					break
			else:
				for i in range(1, m):
					if A[i][j] > A[i - 1][j]:
						first[i] = True
		return res