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"], and the remaining columns of A are ["b","v"], ["e","y"], and ["f","z"].  (Formally, the c-th column is [A[0][c], A[1][c], ..., A[A.length-1][c]]).
Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.
Return the minimum possible value of D.length.
 
Example 1:
Input: A = ["cba","daf","ghi"]
Output: 1
Explanation: 
After choosing D = {1}, each column ["c","d","g"] and ["a","f","i"] are in non-decreasing sorted order.
If we chose D = {}, then a column ["b","a","h"] would not be in non-decreasing sorted order.

Example 2:
Input: A = ["a","b"]
Output: 0
Explanation: D = {}

Example 3:
Input: A = ["zyx","wvu","tsr"]
Output: 3
Explanation: D = {0, 1, 2}

 
Constraints:

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

Source: leetcode | Difficulty: EASY
Tags: String algorithms

Data structures

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

Solutions:
class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		return sum([list(col) != sorted(col) for col in zip(*A)])


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		if len(A) <= 1:
			return 0
		elif len(A[1]) == 1:
			return 0
		D = []
		for i in range(0, len(A[0])):
			col = [a[i] for a in A]
			col_sort = sorted(col)
			if col != col_sort:
				D.append(i)
		return len(D)


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		n = len(A[0])
		res = 0
		for i in range(n):
			col = [a[i] for a in A]
			if col != sorted(col):
				res += 1
		return res


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		result = 0
		M = len(A[0])
		for i in range(M):
			col = [row[i] for row in A]
			if col != sorted(col):
				result += 1
		return result


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		ans = 0
		for (i, word) in enumerate(zip(*A)):
			for j in range(len(word) - 1):
				if word[j] > word[j + 1]:
					ans += 1
					break
		return ans


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		delete_size = 0
		cols = zip(*A)
		for col in cols:
			for (a, b) in zip(col, col[1:]):
				if a > b:
					delete_size += 1
					break
		return delete_size


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		D = 0
		for col in zip(*A):
			p = chr(0)
			for c in col:
				if c < p:
					D += 1
					break
				p = c
		return D


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		return sum((any((i > j for (i, j) in zip(t, t[1:]))) for t in zip(*A)))


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		count = 0
		length = len(A[0])
		noofstr = len(A)
		for i in range(length):
			increasing = True
			for j in range(1, noofstr):
				if A[j][i] < A[j - 1][i]:
					increasing = False
					break
			if increasing:
				count += 1
		return length - count


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		total_deletes = 0
		for j in range(len(A[0])):
			for i in range(1, len(A)):
				if A[i - 1][j] > A[i][j]:
					total_deletes += 1
					break
		return total_deletes


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		res = []
		rows = len(A)
		cols = len(A[0])
		for c in range(cols):
			for r in range(rows - 1):
				if A[r][c] > A[r + 1][c]:
					res.append(-1)
					break
		return res.count(-1)


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		return sum((not all((c <= d for (c, d) in zip(col, col[1:]))) for col in zip(*A)))


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		n = len(A[0])
		del_indices = []
		for j in range(n):
			for i in range(len(A) - 1):
				if A[i][j] > A[i + 1][j]:
					del_indices.append(j)
					break
			continue
		return len(del_indices)


class Solution(object):

	def minDeletionSize(self, A):
		ans = 0
		for col in zip(*A):
			if any((col[i] > col[i + 1] for i in range(len(col) - 1))):
				ans += 1
		return ans


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		ans = 0
		for col in zip(*A):
			if any((col[i] > col[i + 1] for i in range(len(col) - 1))):
				ans += 1
		return ans


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		c_l = len(A[0])
		A_l = len(A)
		count = 0
		for i in range(c_l):
			string = [col[i] for col in A]
			for j in range(1, A_l):
				if string[j] < string[j - 1]:
					count += 1
					break
		return count


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		count = 0
		for col in zip(*A):
			if list(col) != sorted(col):
				count += 1
		return count


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		rows = len(A)
		cols = len(A[0])
		out = []
		for i in range(cols):
			temp = []
			for j in range(rows):
				temp.append(A[j][i])
			out.append(temp)
		count = 0
		for i in out:
			if i != sorted(i):
				count += 1
		return count


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		columns = [''] * len(A[0])
		for string in A:
			for (i, char) in enumerate(string):
				columns[i] += char
		count = 0
		for word in columns:
			if word != ''.join(sorted(word)):
				count += 1
		return count


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		l = list(A[0])
		for i in A:
			for j in range(len(i)):
				if l[j] == 'A':
					continue
				if i[j] < l[j]:
					l[j] = 'A'
				else:
					l[j] = i[j]
		return l.count('A')


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		indiciesToRemove = []
		columns = len(A[0])
		rows = len(A)
		for col in range(0, columns):
			previous = chr(0)
			for row in range(0, rows):
				if A[row][col] < previous:
					indiciesToRemove.append(col)
					break
				previous = A[row][col]
		return len(indiciesToRemove)


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		return sum(([x[i] for x in A] != sorted([x[i] for x in A]) for i in range(len(A[0]))))


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		set_dim = 0
		for column in range(len(A[0])):
			for row in range(len(A) - 1):
				if A[row][column] > A[row + 1][column]:
					set_dim += 1
					break
		return set_dim


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		count = 0
		for c in range(len(A[0])):
			for i in range(len(A) - 1):
				if ord(A[i][c]) > ord(A[i + 1][c]):
					count += 1
					break
		return count


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		do_not_remove_idx = []
		for idx in range(len(A[0])):
			tmp = [a[idx] for a in A]
			if any((x > y for (x, y) in zip(tmp, tmp[1:]))):
				do_not_remove_idx.append(idx)
		return len(do_not_remove_idx)


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		m = len(A)
		n = len(A[0])
		res = 0
		for j in range(n):
			for i in range(m - 1):
				if A[i][j] > A[i + 1][j]:
					res += 1
					break
		return res


class Solution:

	def minDeletionSize(self, A):
		return sum((list(col) != sorted(col) for col in zip(*A)))


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		t = 0
		i = 0
		while i < len(A[0]):
			j = 0
			last = chr(0)
			while j < len(A):
				if A[j][i] >= last:
					last = A[j][i]
				else:
					t += 1
					break
				j += 1
			i += 1
		return t


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		count = 0
		for i in range(len(A[0])):
			if not self.isSorted(list([x[i] for x in A])):
				count += 1
		return count

	def isSorted(self, list_char):
		for i in range(1, len(list_char)):
			if list_char[i - 1] > list_char[i]:
				return False
		return True


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		result = 0
		for i in range(len(A[0])):
			last = A[0][i]
			for j in range(1, len(A)):
				if ord(last) > ord(A[j][i]):
					result += 1
					break
				last = A[j][i]
		return result


class Solution:

	def minDeletionSize(self, A):
		word_len = len(A[0])
		count = 0
		for j in range(word_len):
			for i in range(1, len(A)):
				if A[i][j] < A[i - 1][j]:
					count += 1
					break
		return count


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		if len(A) == 0:
			return 0
		n = len(A[0])
		cnt = 0
		for i in range(n):
			is_sorted = True
			for j in range(len(A) - 1):
				if A[j][i] > A[j + 1][i]:
					is_sorted = False
					break
			if not is_sorted:
				cnt += 1
		return cnt


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		if not A:
			return 0
		count = 0
		prev = ''
		for i in range(0, len(A[0])):
			for j in range(1, len(A)):
				if ord(A[j - 1][i]) > ord(A[j][i]):
					count += 1
					break
		return count


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		count = 0
		for i in zip(*A):
			if ''.join(i) != ''.join(sorted(list(map(''.join, i)))):
				count += 1
		return count


class Solution:

	def findAllPeaks(self, A: List[str]) -> set():
		if len(A[0]) <= 1:
			return set()
		column_number = len(A[0])
		row_number = len(A)
		pre_letter_to_int = [-1 for i in range(column_number)]
		result = set()
		for c in range(column_number):
			for r in range(row_number):
				if ord(A[r][c]) < pre_letter_to_int[c]:
					result.add(c)
					break
				else:
					pre_letter_to_int[c] = ord(A[r][c])
		return result

	def minDeletionSize(self, A: List[str]) -> int:
		return len(self.findAllPeaks(A))


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		size = len(A[0])
		setd = set([i for i in range(size)])
		for i in range(len(A) - 1):
			if not setd:
				return size
			setn = set()
			for digit in setd:
				if A[i][digit] > A[i + 1][digit]:
					setn.add(digit)
			setd -= setn
		return size - len(setd)


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		return sum((any((A[j][i] < A[j - 1][i] for j in range(1, len(A)))) for i in range(len(A[0]))))


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		for i in range(len(A)):
			self.convertCharsToIntArray(i, A)
		counts = 0
		for i in range(len(A[0])):
			checker = False
			for j in range(1, len(A)):
				if A[j - 1][i] > A[j][i]:
					checker = True
			if checker:
				counts += 1
		return counts

	def convertCharsToIntArray(self, i, A):
		chars = A[i]
		array = []
		for char in chars:
			array.append(ord(char))
		A[i] = array


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		count = 0
		col = 0
		while col < len(A[0]):
			row = 0
			while row < len(A) - 1:
				if ord(A[row][col]) > ord(A[row + 1][col]):
					count += 1
					break
				row += 1
			col += 1
		return count


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		ans = []
		j = 0
		for i in range(len(A[0])):
			temp = []
			for k in range(len(A)):
				temp.append(A[k][j])
			ans.append(temp)
			j += 1
		count = 0
		for i in ans:
			temp = i[:]
			temp.sort()
			if temp != i:
				count += 1
		return count


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		count = 0
		for i in range(0, len(A[0])):
			maximum = A[0][i]
			inDecreasingOrder = True
			j = 1
			while j < len(A):
				val = A[j][i]
				if val < maximum:
					inDecreasingOrder = False
					break
				maximum = val
				j += 1
			if inDecreasingOrder:
				count += 1
		return len(A[0]) - count


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		ans = 0
		for i in zip(*A):
			if list(i) != sorted(i):
				ans += 1
		return ans


class Solution:

	def minDeletionSize(self, A: List[str]) -> int:
		prev = A[0]
		indices = {i for i in range(len(prev))}
		remove = set()
		for a in A[1:]:
			remove.clear()
			for i in indices:
				if prev[i] > a[i]:
					remove.add(i)
			indices -= remove
			prev = a
		return len(prev) - len(indices)