You are given an n × m rectangular table consisting of lower case English letters. In one operation you can completely remove one column from the table. The remaining parts are combined forming a new table. For example, after removing the second column from the table

abcd

edfg

hijk



 

we obtain the table:

acd

efg

hjk



 

A table is called good if its rows are ordered from top to bottom lexicographically, i.e. each row is lexicographically no larger than the following one. Determine the minimum number of operations of removing a column needed to make a given table good.


-----Input-----

The first line contains two integers  — n and m (1 ≤ n, m ≤ 100).

Next n lines contain m small English letters each — the characters of the table.


-----Output-----

Print a single number — the minimum number of columns that you need to remove in order to make the table good.


-----Examples-----
Input
1 10
codeforces

Output
0

Input
4 4
case
care
test
code

Output
2

Input
5 4
code
forc
esco
defo
rces

Output
4



-----Note-----

In the first sample the table is already good.

In the second sample you may remove the first and third column.

In the third sample you have to remove all the columns (note that the table where all rows are empty is considered good by definition).

Let strings s and t have equal length. Then, s is lexicographically larger than t if they are not equal and the character following the largest common prefix of s and t (the prefix may be empty) in s is alphabetically larger than the corresponding character of t.

Source: codeforces | Difficulty: MEDIUM
Tags: Complete search

Implementation

Constructive algorithms


Solutions:
def remove(p, a):
	for i in range(len(a)):
		a[i] = a[i][:p] + a[i][p + 1:]
(n, m) = [int(x) for x in input().split()]
a = []
for i in range(n):
	a.append(input())
removed = 0
for i in range(m):
	i -= removed
	for j in range(n - 1):
		if a[j][:i + 1] > a[j + 1][:i + 1]:
			remove(i, a)
			removed += 1
			break
print(removed)


read = lambda : map(int, input().split())
(n, m) = read()
a = [input() for i in range(n)]
ans = 0
ind = [i for i in range(1, n)]
for i in range(m):
	ind2 = []
	for j in ind:
		if a[j][i] < a[j - 1][i]:
			ans += 1
			break
		elif a[j][i] == a[j - 1][i]:
			ind2.append(j)
	else:
		ind = ind2[:]
print(ans)


def main():
	(n, m) = list(map(int, input().split()))
	l = [input() for _ in range(n)]
	lead = [[] for _ in range(n)]
	x = 0
	for nn in zip(*l):
		for (l, c) in zip(lead, nn):
			l.append(c)
		if tuple((l[-1] for l in sorted(lead))) != nn:
			x += 1
			for l in lead:
				del l[-1]
	print(x)

def __starting_point():
	main()
__starting_point()


(n, m) = list(map(int, input().split()))
words = [input() for _ in range(n)]
i = 1
ans = 0
while True:
	if i > len(words[0]):
		break
	for j in range(n - 1):
		if words[j][:i] > words[j + 1][:i]:
			ans += 1
			words = [x[:i - 1] + x[i:] for x in words]
			i -= 1
			break
	i += 1
print(ans)


(n, m) = map(int, input().split())
t = [input() for i in range(n)]
p = [''] * n
s = r = 0
for k in range(m):
	b = p[0] + t[0][k]
	for j in range(1, n):
		(a, b) = (b, p[j] + t[j][k])
		if a > b:
			s += 1
			break
	if r < s:
		r = s
	else:
		for j in range(n):
			p[j] += t[j][k]
print(s)


(n, m) = map(int, input().split())
a = [input() for i in range(n)]
c = 0
for j in range(m):
	b = False
	for i in range(n - 1):
		if a[i] > a[i + 1] and a[i][j] > a[i + 1][j]:
			b = True
			break
	if b:
		c += 1
		for i in range(n):
			a[i] = a[i][:j] + '-' + a[i][j + 1:]
print(c)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = []
for x in range(n):
	s.append(input().strip())
f = [''] * n
ans = 0
for x in range(m):
	t = [f[i] + s[i][x] for i in range(n)]
	if t == sorted(t):
		f = t
	else:
		ans += 1
print(ans)


def get_str_col(arr, i):
	return ''.join([row[i] for row in arr])
(n, m) = map(int, input().split())
(s, ans, tem) = ([input() for i in range(n)], 0, '')
for i in range(m):
	tem = get_str_col(s, i)
	if tem == ''.join(sorted(tem)):
		break
	else:
		ans += 1
con = list(tem)
for i in range(ans + 1, m):
	tem2 = get_str_col(s, i)
	for j in range(n):
		con[j] += tem2[j]
	if sorted(con) != con:
		ans += 1
		for j in range(n):
			con[j] = con[j][:-1]
print(ans)


def lexyco(table, pos):
	for i in range(len(table) - 1):
		for s2 in table[i + 1:]:
			if table[i][:pos + 1] > s2[:pos + 1]:
				return False
	return True
(n, m) = map(int, input().split())
table = []
for i in range(n):
	table.append(input())
cnt = 0
i = 0
while i < len(table[0]):
	if lexyco(table, i):
		i += 1
	else:
		cnt += 1
		for s in range(len(table)):
			table[s] = table[s][:i] + table[s][i + 1:]
print(cnt)


(n, m) = map(int, input().split())
(words, needed, final) = ([input().strip() for _ in range(n)], 0, ['' for _ in range(n)])
for i in range(m):
	extended = [final[j] + words[j][i] for j in range(n)]
	if extended == list(sorted(extended)):
		final = extended
	needed += int(not extended == list(sorted(extended)))
print(needed)


def sortedx(lst):
	copy = lst[:]
	copy.sort()
	if copy == lst:
		return True
	return False
(a, b) = map(int, input().split(' '))
words = [input() for i in range(a)]
each = ['' for i in range(a)]
for j in range(b):
	if sortedx([each[i] + words[i][j] for i in range(a)]):
		for ix in range(a):
			each[ix] = each[ix] + words[ix][j]
print(b - len(each[0]))


(n, m) = map(int, input().split(' '))
masstr = []
good = [[] for i in range(n)]
for i in range(n):
	mas = list(str(input()))
	masstr.append(mas)
for nomer_stolb in range(m):
	tmp = []
	for (i, stroka) in enumerate(good):
		tmp.append(stroka + [masstr[i][nomer_stolb]])
	if sorted(tmp) == tmp:
		good = tmp
print(m - len(good[0]))


def solve():
	(n, m) = map(int, input().split())
	s = [input() for i in range(n)]
	f = ['' for i in range(n)]
	ans = 0
	for i in range(m):
		t = [f[j] + s[j][i] for j in range(n)]
		if t == sorted(t):
			f = t
		else:
			ans += 1
	print(ans)
solve()


import sys, heapq, math
from collections import defaultdict, deque
input = sys.stdin.readline
(r, c) = map(int, input().split())
grid = []
for i in range(r):
	grid.append(input().strip())
equal = [0 for _ in range(c)]
less = [0 for _ in range(c)]
for i in range(c):
	for row in range(1, r):
		if grid[row - 1][i] == grid[row][i]:
			equal[i] = 1
		elif grid[row - 1][i] > grid[row][i]:
			equal[i] = 0
			break
	less[i] = 1
	for row in range(1, r):
		if equal[i] == 1:
			less[i] = 0
			break
		elif grid[row - 1][i] > grid[row][i]:
			less[i] = 0
			break
ans = 0
for i in range(c):
	if less[i] == 1:
		ans = max(ans, c - i)
		break
	elif equal[i] == 1:
		cnt = 1
		l = []
		for row in range(1, r):
			if grid[row - 1][i] == grid[row][i]:
				start = row - 1
				while row < r and grid[row - 1] == grid[row][i]:
					row += 1
				end = row
				l.append([start, end])
		for col in range(i + 1, c):
			f = 0
			ptr = 0
			while ptr < len(l):
				(start, end) = l[ptr]
				ptr += 1
				for row in range(start + 1, end + 1):
					if grid[row - 1][col] > grid[row][col]:
						f = 1
						break
				if f == 1:
					break
			if f == 0:
				cnt += 1
				ptr = 0
				nl = []
				while ptr < len(l):
					(start, end) = l[ptr]
					ptr += 1
					for row in range(start + 1, end + 1):
						if grid[row - 1][col] == grid[row][col]:
							s1 = row - 1
							while row < end + 1 and grid[row - 1] == grid[row][col]:
								row += 1
							e1 = row
							nl.append([s1, e1])
				l = nl
		ans = max(ans, cnt)
print(c - ans)


from __future__ import print_function
from collections import Counter, OrderedDict
from itertools import permutations as perm
from fractions import Fraction
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
(n, m) = gil()
s = []
for _ in range(n):
	s.append(g())
ans = 0
diff = [False] * n
diff[0] = True
for j in range(m):
	isSorted = True
	ifPartiallySorted = True if ans else False
	for i in range(1, n):
		isSorted &= s[i][j] >= s[i - 1][j]
		ifPartiallySorted &= diff[i] | (s[i][j] >= s[i - 1][j])
	if isSorted:
		ans += 1
		for i in range(1, n):
			diff[i] |= s[i][j] > s[i - 1][j]
	elif ifPartiallySorted:
		ans += 1
		for i in range(1, n):
			diff[i] |= s[i][j] > s[i - 1][j]
print(m - ans)


def main():
	(n, m) = map(int, input().split())
	a = [input() for x in range(n)]
	s = [''] * n
	ans = 0
	for i in range(m):
		ts = [s[j] + a[j][i] for j in range(n)]
		if ts == sorted(ts):
			s = ts
		else:
			ans += 1
	print(ans)
main()


def kkr():
	(n, m) = [int(i) for i in input().split()]
	a = []
	for i in range(n):
		a.append([i for i in input()])
	ans = 0
	for i in range(m):
		for j in range(n - 1):
			if a[j][:i + 1] > a[j + 1][:i + 1]:
				for k in range(n):
					a[k][i] = 'z'
				ans += 1
				break
	print(ans)
kkr()


(n, m) = map(int, input().split())
txt = [input() for _ in range(n)]
sol = 0
pof = list(range(n - 1))
for i in range(m):
	cli = [rw[i] for rw in txt]
	of = [x for (x, y) in zip(pof, [i + 1 for i in pof]) if cli[x] > cli[y]]
	if len(of) > 0:
		sol += 1
		continue
	nf = [x for (x, y) in zip(pof, [i + 1 for i in pof]) if cli[x] < cli[y]]
	pof = [t for t in pof if t not in nf]
print(sol)


line = input().split()
n = int(line[0])
m = int(line[1])
data = []
for i in range(n):
	data.append(input())
x = [1 for i in range(n)]
delete = 0
for i in range(m):
	dum = [1 for j in range(n)]
	status = 1
	for j in range(1, n):
		if data[j][i] > data[j - 1][i]:
			dum[j] = 0
		elif data[j][i] == data[j - 1][i]:
			dum[j] = 1
		elif x[j] == 1:
			delete += 1
			status = 0
			break
	if status == 1:
		for j in range(len(dum)):
			if dum[j] == 0:
				x[j] = 0
print(delete)


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, input().split()))

def prev(rr, p):
	for col in range(p - 1, -1, -1):
		if col in rem:
			continue
		if s[rr][col] > s[rr - 1][col]:
			return True
	return False
for i in range(1):
	(r, c) = lst()
	rem = set()
	s = [input() for _ in range(r)]
	first_valid_col = -1
	for col in range(c):
		f = 1
		for i in range(1, r):
			if s[i][col] < s[i - 1][col]:
				rem.add(col)
				f = 0
				break
		if f:
			first_valid_col = col
			break
	if first_valid_col == -1:
		print(c)
		continue
	for col in range(first_valid_col + 1, c):
		for i in range(1, r):
			if prev(i, col) == False and s[i][col] < s[i - 1][col]:
				rem.add(col)
				break
	print(len(rem))


from collections import defaultdict, deque

def main():
	(n, m) = map(int, input().split())
	a = [[c for c in input()] for i in range(n)]
	che = [[0 for i in range(n + 2)] for j in range(n + 2)]
	ans = 0
	for j in range(m):
		check = False
		for i in range(n - 1):
			if a[i][j] > a[i + 1][j]:
				if not che[i][i + 1]:
					ans += 1
					check = True
					break
		if not check:
			for i in range(n - 1):
				if a[i][j] < a[i + 1][j]:
					che[i][i + 1] = 1
	print(ans)
main()


import sys
import bisect
from random import randint
input = lambda : sys.stdin.readline().strip('\r\n')
from math import gcd
sa = lambda : input()
sb = lambda : int(input())
sc = lambda : input().split()
sd = lambda : list(map(int, input().split()))
se = lambda : float(input())
sf = lambda : list(input())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7

def hnbhai():
	(n, m) = sd()
	s = []
	for i in range(n):
		s.append(sa())
	ans = 0
	row = [0] * n
	for i in range(m):
		f = 0
		for j in range(n - 1):
			if row[j] == 0 and s[j][i] > s[j + 1][i]:
				ans += 1
				f = 1
				break
		if f == 0:
			for j in range(n - 1):
				if s[j][i] < s[j + 1][i]:
					row[j] = 1
	print(ans)
for _ in range(1):
	hnbhai()


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, l) = value()
ans = set()
s = []
for _ in range(n):
	s.append(input())
checked = defaultdict(bool)
for i in range(l):
	sort = True
	for j in range(1, n):
		if s[j][i] < s[j - 1][i] and (not checked[s[j - 1]]):
			sort = False
			ans.add(i)
			break
	if sort:
		for j in range(1, n):
			if s[j][i] > s[j - 1][i]:
				checked[s[j - 1]] = True
print(len(ans))


def issorted(l):
	return all((l[i] <= l[i + 1] for i in range(len(l) - 1)))

def mainX(n, m, t):
	ans = 0
	while not issorted(t):
		remove = -1
		for i in range(len(t) - 1):
			if t[i] > t[i + 1]:
				for j in range(len(t[i])):
					if t[i][j] != t[i + 1][j]:
						remove = j
						break
			if remove != -1:
				print(i, remove)
				break
		t = [_t[:remove] + _t[remove + 1:] for _t in t]
		ans += 1
	print(ans)

def is_good(s):
	return all((s[i] <= s[i + 1] for i in range(len(s) - 1)))

def line_is_good(a, j):
	return all((a[i][j] <= a[i + 1][j] for i in range(len(a) - 1)))

def main5(n, m, a):
	if n <= 1 or m <= 0 or is_good(a):
		print(0)
		return
	bad = []
	for i in range(0, m):
		if line_is_good(a, i):
			continue
		s = [''.join([k for (b, k) in enumerate(x) if b not in bad]) for x in a]
		print(i, bad)
		if is_good(s):
			print(len(bad))
			return
		else:
			bad.append(i)
	print(m)

def main6(n, m, a):
	if n <= 1 or m <= 0 or is_good(a):
		print(0)
		return
	bad = []
	good = list(range(m))
	ans = 0
	while not is_good(a):
		remove = -1
	return
	for i in range(0, m):
		if line_is_good(a, i):
			continue
		bad.append(i)
		s = [''.join([k for (b, k) in enumerate(x) if b not in bad]) for x in a]
		if is_good(s):
			print(len(bad))
			return
	print(m)

def main(n, m, a):
	if n <= 1 or m <= 0 or is_good(a):
		print(0)
		return
	bad = []
	ans = 0
	while not is_good(a):
		remove = -1
		for i in range(n - 1):
			if a[i] > a[i + 1]:
				for j in range(len(a[i])):
					if a[i][j] > a[i + 1][j]:
						remove = j
						break
			if remove != -1:
				break
		a = [x[:remove] + x[remove + 1:] for x in a]
		ans += 1
	print(ans)

def main_input():
	(n, m) = [int(i) for i in input().split()]
	a = [input() for s in range(n)]
	main(n, m, a)

def __starting_point():
	main_input()
__starting_point()


(n, m) = map(int, input().split())
grid = []
for _ in range(n):
	grid.append(list(input()))
deleted = 0
last = []
for j in range(m):
	for i in range(1, n):
		if grid[i][j] < grid[i - 1][j] and len(last) == 0:
			deleted += 1
			break
		elif len(last) and grid[i][j] < grid[i - 1][j]:
			if ''.join((grid[i - 1][x] for x in last + [j])) > ''.join((grid[i][x] for x in last + [j])):
				deleted += 1
				break
	else:
		last.append(j)
print(deleted)


__author__ = 'trunghieu11 - vuondenthanhcong11@gmail.com'

def read_int():
	return int(input())

def read_ints():
	return map(int, input().split())

def read_list_int():
	return list(map(int, input().split()))

def read_strings(row_count):
	answer = []
	for i in range(0, row_count):
		answer.append(input())
	return answer
(row_count, column_count) = read_ints()
table = read_strings(row_count)
save = set()
answer = 0
for j in range(0, column_count):
	isOk = True
	for i in range(1, row_count):
		if table[i][j] < table[i - 1][j] and i - 1 << 15 | i not in save:
			isOk = False
			answer += 1
			break
	if isOk:
		for i in range(1, row_count):
			if table[i][j] > table[i - 1][j]:
				save.add(i - 1 << 15 | i)
print(answer)


s = input()
s = s.split()
n = int(s[0])
m = int(s[1])
l = []
for i in range(0, n):
	s = input()
	l.append(s)
cont = 0
ant = 0
i = 0
while i < n:
	if l[ant] > l[i]:
		for k in range(0, n):
			l[k] = list(l[k])
		achou = False
		j = 0
		for j in range(0, m):
			if l[ant][j] > l[i][j]:
				achou = True
				break
		for k in range(0, n):
			l[k].pop(j)
			l[k] = ''.join(l[k])
		i = 0
		ant = 0
		m -= 1
		cont += 1
	else:
		ant = i
		i += 1
print(cont)


(n, m) = map(int, input().split())
ans = 0
st = [input() for i in range(n)]
new = [''] * n
for i in range(m):
	newstr = [new[j] + st[j][i] for j in range(n)]
	if newstr == sorted(newstr):
		new = newstr
	else:
		ans += 1
print(ans)


def input_split(f):
	return map(f, input().split())

def main():
	(n, m) = input_split(int)
	lst = [input()]
	sml = []
	for i in range(n - 1):
		lst.append(input())
		sml.append(False)
	ans = 0
	for i in range(m):
		flag = True
		for j in range(n - 1):
			flag = flag and (lst[j][i] <= lst[j + 1][i] or sml[j])
		if flag:
			for j in range(n - 1):
				if lst[j][i] < lst[j + 1][i]:
					sml[j] = True
		else:
			ans += 1
	print(ans)
main()


import sys
import math
MAXNUM = math.inf
MINNUM = -1 * math.inf
ASCIILOWER = 97
ASCIIUPPER = 65

def getInt():
	return int(sys.stdin.readline().rstrip())

def getInts():
	return map(int, sys.stdin.readline().rstrip().split(' '))

def getString():
	return sys.stdin.readline().rstrip()

def printOutput(ans):
	sys.stdout.write()
	pass

def orderedVal(grid, curValues, column):
	if column == 0:
		return 0
	for i in range(len(grid)):
		if grid[i][curValues] > grid[i][column]:
			return math.inf
	return 0

def isLex(grid, column):
	for i in range(1, len(grid)):
		if grid[i][column] < grid[i - 1][column]:
			return False
	return True

def getLexPairs(grid, column):
	lPairs = set()
	for i in range(1, len(grid)):
		if grid[i][column] == grid[i - 1][column]:
			lPairs.add((i - 1, i))
	return lPairs

def compare(grid, column, lPairs):
	nextlPairs = set()
	for (a, b) in lPairs:
		if grid[a][column] > grid[b][column]:
			return False
		elif grid[a][column] == grid[b][column]:
			nextlPairs.add((a, b))
	return nextlPairs

def solve(grid):
	ans = len(grid[0])
	for column in range(len(grid[0])):
		if ans <= column:
			break
		if isLex(grid, column):
			removeCol = 0
			lPairs = getLexPairs(grid, column)
			for nextColumn in range(column + 1, len(grid[0])):
				k = compare(grid, nextColumn, lPairs)
				if k == False:
					removeCol += 1
				elif len(k) == 0:
					break
				else:
					lPairs = k
			ans = min(ans, column + removeCol)
	return ans

def readinput():
	(n, m) = getInts()
	grid = []
	for _ in range(n):
		grid.append(getString())
	print(solve(grid))
readinput()


v = list(input().split())
n = int(v[0])
m = int(v[1])
v = list()
for i in range(n):
	v.append(input())
if n == 1:
	print(0)
	exit()
kll = 0
j = 0
brk = 0
while j < m:
	for i in range(1, n):
		if v[i][:j + 1] < v[i - 1][:j + 1]:
			brk = 1
			break
	if brk:
		for i in range(n):
			tmp = list(v[i])
			tmp.pop(j)
			v[i] = ''.join(tmp)
		kll += 1
		m -= 1
	else:
		j += 1
	brk = 0
print(kll)


(n, m) = map(int, input().split())
L = [input() for i in range(n)]
k = 0
deleted = set()

def chek():
	imun = set()
	global deleted
	global L
	global m
	global n
	for i in range(m):
		if i not in deleted:
			for j in range(1, n):
				if L[j][i] > L[j - 1][i]:
					imun.add(j)
				if L[j][i] < L[j - 1][i] and j not in imun:
					deleted.add(i)
					return True
	return False
b = chek()
while b:
	b = chek()
print(len(deleted))


from operator import itemgetter
(n, m) = map(int, input().strip().split())
table = []
bad_cols = [False] * m
for _ in range(n):
	table.append(input().strip())
for j in range(m):
	indices = [idx for idx in range(j + 1) if not bad_cols[idx]]
	for i in range(1, n):
		if itemgetter(*indices)(table[i]) < itemgetter(*indices)(table[i - 1]):
			bad_cols[j] = True
			break
print(sum(bad_cols))


from math import *
from collections import *
from random import *
from bisect import *
import sys
input = sys.stdin.readline

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())

def inp():
	return int(input())

def fk(a, s, k):
	b = []
	for i in range(len(a)):
		b.append(a[i] + (i + 1) * k)
	b.sort()
	return sum(b[:k])
(n, m) = ma()
re = 0
r = []
co = [''] * n
for i in range(n):
	s = input().rstrip('\n')
	r.append(s)
for i in range(m):
	t = [co[j] + r[j][i] for j in range(n)]
	if t == sorted(t):
		co = t
	else:
		re += 1
print(re)


(n, m) = list(map(int, input().split()))
ls = [input() for _ in range(n)]
sorted_inds = [0] * n
ans = 0
for i in range(m):
	new_sorted_inds = set()
	for j in range(1, n):
		if sorted_inds[j] == 0:
			if ls[j][i] < ls[j - 1][i]:
				ans += 1
				break
	else:
		for j in range(1, n):
			if ls[j][i] > ls[j - 1][i]:
				sorted_inds[j] = 1
print(ans)


from sys import stdin, stdout
from collections import Counter
from itertools import permutations
import bisect
import math
I = lambda : map(int, stdin.readline().split())
I1 = lambda : stdin.readline()
(n, m) = I()
if n == 1:
	print(0)
	exit()
s = [I1() for i in range(n)]
if m == 1:
	if s == sorted(s):
		print(0)
	else:
		print(1)
	exit()
(c, i) = (0, 1)
while True:
	if i > len(s[0]):
		break
	for j in range(n - 1):
		if s[j][:i] > s[j + 1][:i]:
			c += 1
			s = [x[:i - 1] + x[i:] for x in s]
			i -= 1
			break
	i += 1
print(c)


line = input().split()
n = int(line[0])
m = int(line[1])
lst = [input()]
sml = []
for i in range(n - 1):
	lst.append(input())
	sml.append(False)
ans = 0
for i in range(m):
	flag = True
	for j in range(n - 1):
		flag = flag and (lst[j][i] <= lst[j + 1][i] or sml[j])
	if flag:
		for j in range(n - 1):
			if lst[j][i] < lst[j + 1][i]:
				sml[j] = True
	else:
		ans += 1
print(str(ans))


(sizeI, sizeJ) = map(int, input().split())
a = [list(input()) for _ in range(sizeI)]
res = ['' for _ in range(sizeI)]
for col in zip(*a):
	newRes = res[:]
	for (i, c) in enumerate(col):
		newRes[i] += c
	if newRes == sorted(newRes):
		res = newRes[:]
print(sizeJ - len(res[0]))


import sys
(n, m) = [int(i) for i in input().split()]
a = [[0] * n for i in range(m)]
for i in range(n):
	temp = input()
	for j in range(m):
		a[j][i] = temp[j]
c = 0

def blatant(a):
	for i in range(1, len(a)):
		if a[i] < a[i - 1]:
			return True
	return False
match = []
while True:
	if len(a) == 0:
		print(m)
		return
	elif blatant(a[0]):
		del a[0]
		c += 1
	else:
		break
for i in range(1, n):
	if a[0][i] == a[0][i - 1]:
		match.append(i)

def rm(a, match):
	c = 0
	for m in match:
		i = 1
		while i < len(a):
			if a[i][m] < a[i][m - 1]:
				del a[i]
				c += 1
			elif a[i][m] == a[i][m - 1]:
				i += 1
			else:
				break
	return c
while True:
	temp = rm(a, match)
	if temp == 0:
		break
	c += temp
print(c)


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return list(map(str, input().strip()))

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter, deque
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby
from itertools import permutations as comb

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a // gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = I()
	return n

def dfs(i, p):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	if n > 2:
		l.append(n)
	return l
(r, c) = lint()
s = []
s.append(['a'] * (c + 1))
for _ in range(r):
	s.append(['a'] + S())
cnt = 0
k = 0
t = [0] * (r + 1)
for i in range(1, c + 1):
	flag = 0
	for j in range(1, r):
		if not t[j]:
			if ord(s[j + 1][i]) < ord(s[j][i]):
				cnt += 1
				flag = 1
				break
	if not flag:
		for j in range(1, r):
			if s[j][i] < s[j + 1][i]:
				t[j] = 1
print(cnt)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def seive():
	prime = [1 for i in range(10 ** 6 + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(10 ** 6 + 1):
		if prime[i]:
			for j in range(2 * i, 10 ** 6 + 1, i):
				prime[j] = 0
	return prime
(n, m) = L()
A = [input() for i in range(n)]
t = ['' for i in range(n)]
ans = 0
for i in range(m):
	f = [t[j] + A[j][i] for j in range(n)]
	if f == sorted(f):
		t = f
	else:
		ans += 1
print(ans)
endtime = time.time()


def answer(n, m, A):
	s = []
	for j in range(m):
		flag = 1
		for i in range(1, n):
			if A[i][j] >= A[i - 1][j]:
				flag = 1
			elif len(s) > 0:
				for k in s:
					if A[i][k] > A[i - 1][k]:
						flag = 1
						break
					else:
						flag = 0
				if flag == 0:
					break
			else:
				flag = 0
				break
		if flag:
			s.append(j)
	return m - len(s)
(n, m) = map(int, input().split())
arr = []
for i in range(n):
	arr.append(input())
print(answer(n, m, arr))


(n, m) = list(map(int, input().rstrip().split()))
words = []
op = 0
for i in range(n):
	words += [input()]
final = [''] * n
for j in range(m):
	flag = 1
	for i in range(n - 1):
		x = final[i] + words[i][j]
		y = final[i + 1] + words[i + 1][j]
		if x > y:
			op += 1
			flag = 0
			break
	if flag == 1:
		for i in range(n):
			final[i] += words[i][j]
print(op)


import sys
from collections import deque
import math
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
li = lambda : list(input_())
pr = lambda x: print(x)
f = lambda : sys.stdout.flush()
(n, m) = il()
ans = 0
a = []
for _ in range(n):
	a.append(ip())
b = ['' for _ in range(n)]
for i in range(m):
	c = []
	for j in range(n):
		c.append(b[j] + a[j][i])
	if c == sorted(c):
		if len(c) == len(set(c)):
			break
		else:
			b = c
	else:
		ans += 1
print(ans)


def is_lexigraphic(s):
	for i in range(len(s) - 1):
		if s[i] > s[i + 1]:
			return False
	return True
I = lambda : list(map(int, input().split()))
(n, m) = I()
a = [input() for i in range(n)]
mn = m
columns = list(zip(*a))
for i in range(m):
	curCol = columns[i]
	if not is_lexigraphic(curCol):
		continue
	l = []
	for j in range(n - 1):
		if curCol[j] == curCol[j + 1]:
			l.append(j)
	x = 0
	for k in range(i + 1, m):
		if any([columns[k][a] > columns[k][a + 1] for a in l]):
			x += 1
		elif any([columns[k][a] == columns[k][a + 1] for a in l]):
			l = [a for a in l if columns[k][a] == columns[k][a + 1]]
		else:
			break
	mn = min(x + i, mn)
print(mn)


R = lambda : map(int, input().split())
(n, m) = R()
strs = [input() for i in range(n)]
res = 0
for j in range(m):
	base = ['' for _ in range(n)]
	for j2 in range(j, m):
		nxt = [base[r] + strs[r][j2] for r in range(n)]
		if len(nxt) <= 1 or all((s1 <= s2 for (s1, s2) in zip(nxt, nxt[1:]))):
			base = nxt
	res = max(res, len(base[0]))
print(m - res)


(n, m) = map(int, input().split())
table = [input() for i in range(n)]
ans = 0
ar = [1] * n
for i in range(m):
	ar2 = [ar[i] for i in range(n)]
	flag = 1
	for j in range(1, n):
		if ar[j]:
			if table[j][i] > table[j - 1][i]:
				ar2[j] = 0
			elif table[j][i] < table[j - 1][i]:
				ans += 1
				flag = 0
				break
	if flag:
		ar = [ar2[i] for i in range(n)]
print(ans)


def solve(n, m, ar):
	cnt = 0
	index = 0
	if n == 1:
		print(0)
		return
	flag = 0
	while index < len(ar[0]):
		k = 0
		for i in range(n - 1):
			if ar[i][:index + 1] <= ar[i + 1][:index + 1]:
				continue
			else:
				cnt += 1
				flag = 1
				while k != n:
					ar[k] = ar[k][:index] + ar[k][index + 1:]
					k += 1
				break
		if flag == 1:
			flag = 0
			continue
		else:
			index += 1
	print(cnt)
(n, m) = map(int, input().split())
ar = []
for _ in range(n):
	ar.append(list(input()))
solve(n, m, ar)


I = lambda : list(map(int, input().split()))
(n, m) = I()
ans = 0
columns = list(zip(*[input() for i in range(n)]))
g = [0 for _ in range(n)]
for column in columns:
	if sum((g[i] or column[i] <= column[i + 1] for i in range(n - 1))) == n - 1:
		for i in range(n - 1):
			g[i] |= column[i] < column[i + 1]
	else:
		ans += 1
print(ans)


(n, m) = [int(x) for x in input().split()]
rs = [input() for _ in range(n)]
mask = [1] * m

def get_masked(x):
	return ''.join((y for (y, m) in zip(x, mask) if m))
res = 0
for i in range(m):
	l = [get_masked(x)[:i - res + 1] for x in rs]
	if not all((l[i] <= l[i + 1] for i in range(len(l) - 1))):
		mask[i] = 0
		res += 1
print(res)


R = input
(n, m) = map(int, R().split())
N = range(n)
v = zip(*map(list, [R() for _ in N]))
g = [0] * n
s = 0
for r in v:
	if sum((g[i] or r[i] >= r[i - 1] for i in N[1:])) < n - 1:
		s += 1
	else:
		for i in N[1:]:
			g[i] |= r[i] > r[i - 1]
print(s)