Given a list of words, each word consists of English lowercase letters.
Let's say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2.  For example, "abc" is a predecessor of "abac".
A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.
Return the longest possible length of a word chain with words chosen from the given list of words.
 
Example 1:
Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

 
Note:

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of English lowercase letters.

Difficulty: MEDIUM
Tags: String algorithms

Data structures

Dynamic programming

Amortized analysis
Skill types: Dynamic programming

Amortized analysis

Data structures

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

Solutions:
class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		by_length = collections.defaultdict(set)
		for word in words:
			by_length[len(word)].add(word)
		longest = 1
		seen = {*()}
		mx = len(by_length)
		mn = min(by_length)
		for length in sorted(by_length, reverse=True):
			if length - mn < longest:
				break
			for word in by_length[length]:
				if length - mn < longest:
					break
				if word in seen:
					continue
				stk = [(word, length, 1)]
				while stk:
					(word, k, n) = stk.pop()
					seen.add(word)
					if n > longest:
						longest = n
					for i in range(k):
						pre = word[:i] + word[i + 1:]
						if pre not in seen and pre in by_length[k - 1]:
							stk.append((pre, k - 1, n + 1))
				if longest == mx:
					return longest
		return longest


class Solution:

	def issubsequence(self, str1, str2):
		str1_pointer = 0
		for i in range(len(str2)):
			if str2[i] == str1[str1_pointer]:
				str1_pointer += 1
			if str1_pointer == len(str1):
				return True
		return False

	def longestStrChain(self, words: List[str]) -> int:
		word_lengths = {}
		for i in words:
			if len(i) not in word_lengths:
				word_lengths[len(i)] = [i]
			else:
				word_lengths[len(i)].append(i)
		max_length = max(list(word_lengths.keys()))

		@lru_cache(None)
		def dp(word):
			if len(word) not in word_lengths:
				return 0
			if len(word) == max_length:
				return 1
			else:
				max_chain = 1
				for i in word_lengths[len(word) + 1]:
					if self.issubsequence(word, i):
						max_chain = max(max_chain, 1 + dp(i))
				return max_chain
		res = 0
		for i in words:
			res = max(res, dp(i))
		return res


class Solution:
	_max = 0

	def longestStrChain(self, words: List[str]) -> int:

		def dfs(cur, step):
			if cur not in s:
				return
			if len(cur) == 0:
				return
			self._max = max(step, self._max)
			for i in range(len(cur)):
				t = cur[:i] + cur[i + 1:]
				dfs(t, step + 1)
		s = set(words)
		for w in sorted(words, key=len, reverse=True):
			dfs(w, 1)
		return self._max


from collections import defaultdict

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = defaultdict(lambda : 0)
		for word in sorted(words, key=len):
			dp[''.join(sorted(word))] = max((dp[''.join(sorted(word[:idx] + word[idx + 1:]))] for idx in range(len(word)))) + 1
		return max(dp.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def compare(s1, s2):
			if abs(len(s1) - len(s2)) != 1:
				return False
			if len(s2) > len(s1):
				(s1, s2) = (s2, s1)
			broke = False
			(s1, s2) = (list(s1), list(s2))
			while s1 and s2:
				(a, b) = (s1.pop(), s2.pop())
				if a != b:
					if broke or s1.pop() != b:
						return False
					broke = True
			return True
		G = collections.defaultdict(list)
		i = float('inf')
		j = float('-inf')
		for w in words:
			i = min(i, len(w))
			j = max(j, len(w))
			G[len(w)].append((w, 1))
		res = 1
		m = i + 1
		while m <= j:
			for (a, w1) in enumerate(G[m]):
				for (b, w2) in enumerate(G[m - 1]):
					if compare(w1[0], w2[0]):
						G[m][a] = (w1[0], 1 + w2[1])
						res = max(1 + w2[1], res)
			m += 1
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def precedent(w1_c, w2_c):
			if len(w1_c) > len(w2_c):
				return False
			count = 0
			for c in w2_c:
				if c in w1_c:
					count += w2_c[c] - w1_c[c]
				else:
					count += w2_c[c]
			return count == 1
		minL = float('inf')
		maxL = float('-inf')
		longest = 1
		len_count = collections.defaultdict(list)
		subsequent_of_word = collections.defaultdict(int)
		count_of_word = collections.defaultdict(Counter)
		for w in words:
			len_count[len(w)].append(w)
			subsequent_of_word[w] = 1
			count_of_word[w] = Counter(w)
			maxL = max(maxL, len(w))
			minL = min(minL, len(w))
		for i in range(maxL - 1, minL - 1, -1):
			if i in len_count:
				if i + 1 in len_count:
					for w1 in len_count[i]:
						for w2 in len_count[i + 1]:
							if precedent(count_of_word[w1], count_of_word[w2]):
								subsequent_of_word[w1] = max(subsequent_of_word[w1], subsequent_of_word[w2] + 1)
								longest = max(longest, subsequent_of_word[w1])
				else:
					for w in len_count[i]:
						subsequent_of_word[w] = 1
		return longest


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x), reverse=True)
		minLen = len(words[-1])
		dic = set(words)
		seen = set()
		self.result = 0
		for word in words:
			if word not in seen:
				length = 1
				self.dfs(word, dic, seen, minLen, length)
		return self.result

	def dfs(self, word, dic, seen, minLen, length):
		self.result = max(self.result, length)
		if len(word) == minLen:
			return
		seen.add(word)
		for i in range(len(word)):
			new = word[:i] + word[i + 1:]
			if new in dic:
				self.dfs(new, dic, seen, minLen, length + 1)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		all_chains = []
		for word in words:
			all_chains.extend(self.createChains(word, words))
		return max(map(len, all_chains))

	def createChains(self, word, words):
		result = []
		step = [word]
		dictionary = set(words)
		self.helper(word, step, dictionary, result)
		return result

	def helper(self, word, step, dictionary, result):
		result.append(step[:])
		for i in range(len(word) - 1, -1, -1):
			substring = word[:i] + word[i + 1:]
			if substring in dictionary:
				step.append(substring)
				self.helper(substring, step, dictionary, result)
				step.pop()


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		self._len_to_words = collections.defaultdict(list)
		for w in words:
			self._len_to_words[len(w)].append(w)
		self._cache = {}
		self._visited = {}
		max_so_far = 0
		for w in words:
			max_so_far = max(max_so_far, self._find_longest(w))
		return max_so_far

	def _find_longest(self, w):
		if w in self._visited:
			return self._visited[w]
		len_w = len(w)
		if len_w + 1 not in self._len_to_words:
			self._visited[w] = 1
			return 1
		max_chain_len = 1
		for cand in self._len_to_words[len_w + 1]:
			if self.is_predecessor(w, cand):
				max_chain_len = max(max_chain_len, 1 + self._find_longest(cand))
		self._visited[w] = max_chain_len
		return max_chain_len

	def is_predecessor(self, w1, w2):
		if (w1, w2) in self._cache:
			return self._cache[w1, w2]
		is_p = True
		if len(w1) + 1 != len(w2):
			is_p = False
		else:
			count = {}
			for c in w1:
				if c in count:
					count[c] += 1
				else:
					count[c] = 1
			found_diff = False
			for c in w2:
				if c in count:
					count[c] -= 1
					if count[c] == 0:
						del count[c]
				elif found_diff:
					is_p = False
					break
				else:
					found_diff = True
					count[c] = 1
		if is_p:
			keys = list(count.keys())
			is_p = len(keys) == 1 and count[keys[0]] == 1
		self._cache[w1, w2] = is_p
		return is_p


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def f(x, y):
			if len(x) != len(y) - 1:
				return False
			p = len(x)
			for i in range(len(x)):
				if x[i] != y[i]:
					p = i
					break
			for i in range(p, len(x)):
				if x[i] != y[i + 1]:
					return False
			return True
		words.sort(key=lambda x: len(x))
		d = {words[i]: i for i in range(len(words))}
		a = []
		for _ in range(len(words)):
			a.append([False] * len(words))
		for j in range(len(words)):
			for k in range(len(words[j])):
				i = d.get(words[j][:k] + words[j][k + 1:], -1)
				if i >= 0:
					a[i][j] = True
		dp = [1] * len(words)
		for i in range(1, len(words)):
			for j in range(i):
				if a[j][i]:
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		hashtable = {}
		record = [1 for i in range(17)]
		for w in words:
			if len(w) not in hashtable:
				hashtable[len(w)] = [{w: 1}]
			else:
				hashtable[len(w)].append({w: 1})
		for i in range(17):
			if i in hashtable:
				if i - 1 in hashtable:
					n = 0
					tmp_max = 0
					for word in hashtable[i]:
						word = list(word.keys())[0]
						m = 0
						for preword in hashtable[i - 1]:
							preword = list(preword.keys())[0]
							if self.ispreword(preword, word):
								hashtable[i][n][word] = max(hashtable[i - 1][m][preword] + 1, hashtable[i][n][word])
								tmp_max = max(tmp_max, hashtable[i][n][word])
							m += 1
						n += 1
					record[i] = tmp_max
		return max(record)

	def ispreword(self, preword, word):
		check = [i for i in word]
		for w in preword:
			if w not in check:
				return False
			else:
				check.remove(w)
		return True


from functools import lru_cache

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		d = collections.defaultdict(list)
		for w in words:
			d[len(w)].append(w)

		@lru_cache(None)
		def dp(w):
			if len(w) == 1:
				return 1
			for candidate in d[len(w) - 1]:
				for i in range(len(w)):
					if candidate == w[:i] + w[i + 1:]:
						return dp(candidate) + 1
			return 1
		return max((dp(i) for i in words))


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		N = len(words)
		if N < 2:
			return N
		words.sort(key=len)
		Table = {word: 1 for word in words}
		result = 1
		for word in words:
			for j in range(len(word)):
				subword = word[:j] + word[j + 1:]
				if subword in Table and Table[subword] >= Table[word]:
					Table[word] = Table[subword] + 1
			if Table[word] > result:
				result = Table[word]
		return result


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		length2words = defaultdict(list)
		for w in words:
			length2words[len(w)].append(w)
		word2chain = dict()
		for l in sorted(length2words):
			for w in length2words[l]:
				word2chain[w] = 1
				if l - 1 not in length2words:
					continue
				for prev_w in length2words[l - 1]:
					if word2chain[prev_w] + 1 < word2chain[w]:
						continue
					if self.isPredecessor(prev_w, w):
						word2chain[w] = max(word2chain[w], word2chain[prev_w] + 1)
		return max(word2chain.values())

	def isPredecessor(self, word1, word2):
		for i in range(len(word2)):
			skip = word2[:i] + word2[i + 1:]
			if skip == word1:
				return True
		return False


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def longest_chain(word, word_set, memo):
			if word not in word_set:
				return 0
			if word not in memo:
				longest = 1
				for i in range(len(word)):
					next_word = word[:i] + word[i + 1:]
					longest = max(1 + longest_chain(next_word, word_set, memo), longest)
				memo[word] = longest
			return memo[word]
		longest = 0
		for word in words:
			longest = max(longest_chain(word, set(words), {}), longest)
		return longest


from collections import defaultdict, deque

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if len(words) <= 1:
			return len(words)
		(graph_dict, len_words_dict) = self.getGraphDict(words)
		word_lengths = list(len_words_dict.keys())
		word_lengths.sort()
		length_index_dict = defaultdict()
		for i in range(len(word_lengths)):
			length_index_dict[word_lengths[i]] = i
		return self.bfsWordChain(graph_dict, len_words_dict, word_lengths, length_index_dict)

	def bfsWordChain(self, graph_dict, len_words_dict, word_lengths, length_index_dict):
		word_lenghts_index = 0
		initial_words = len_words_dict[word_lengths[0]]
		max_possible_length = len(word_lengths)
		curr_length = 1
		visited = set()
		queue = deque()
		for word in initial_words:
			queue.append((word, 1))
			visited.add(word)
		max_len_so_far = 1
		while queue:
			this_item = queue.popleft()
			this_word = this_item[0]
			this_chain_len = this_item[1]
			max_len_so_far = max(max_len_so_far, this_chain_len)
			this_item_possible_length = this_chain_len + len(word_lengths) - length_index_dict[len(this_word)]
			if this_item_possible_length > max_len_so_far:
				neighbors = graph_dict[this_word]
				for neighbor in neighbors:
					if neighbor not in visited:
						visited.add(neighbor)
						queue.append((neighbor, this_chain_len + 1))
				if len(queue) == 0:
					word_found = False
					for word_length in word_lengths:
						for word in len_words_dict[word_length]:
							if word not in visited and (not word_found):
								queue.append((word, 1))
								visited.add(word)
								word_found = True
								break
		return max_len_so_far

	def getGraphDict(self, words):
		len_words_dict = defaultdict(list)
		for word in words:
			len_words_dict[len(word)].append(word)
		word_lenghts_arr = []
		graph_dict = defaultdict(list)
		for word_length in len_words_dict:
			for predecessor in len_words_dict[word_length]:
				if word_length + 1 in len_words_dict:
					for word in len_words_dict[word_length + 1]:
						if self.isPredecessor(predecessor, word):
							graph_dict[predecessor].append(word)
		return (graph_dict, len_words_dict)

	def isPredecessor(self, predecessor, word):
		predecessor_index = 0
		word_index = 0
		while predecessor_index < len(predecessor) and word_index < len(word):
			if predecessor[predecessor_index] == word[word_index]:
				predecessor_index += 1
				word_index += 1
			else:
				word_index += 1
		if word_index == predecessor_index + 1 or word_index == predecessor_index:
			return True
		else:
			return False


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		d = collections.defaultdict(list)
		for word in words:
			d[len(word)].append(word)
		lengths = sorted(list(d.keys()))
		self.mem = {}

		def dfs(word):
			if len(word) == lengths[-1]:
				return 1
			if word in self.mem:
				return self.mem[word]
			nxt_length = 0
			for nxt_word in d[len(word) + 1]:
				for j in range(len(nxt_word)):
					if word == nxt_word[:j] + nxt_word[j + 1:]:
						nxt_length = max(nxt_length, dfs(nxt_word))
			self.mem[word] = nxt_length + 1
			return nxt_length + 1
		res = 0
		for word in words:
			res = max(res, dfs(word))
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		words.sort(key=len)

		def isNeighbor(a, b):
			if len(a) + 1 != len(b):
				return False
			if a == b[1:] or a == b[:-1]:
				return True
			(ia, ib) = (0, 0)
			flag = True
			while ia < len(a):
				if a[ia] == b[ib]:
					(ia, ib) = (ia + 1, ib + 1)
				elif flag:
					flag = False
					ib += 1
				else:
					return False
			return True
		dp = [1] * len(words)
		ans = 0
		for i in range(len(words)):
			for j in range(i):
				if len(words[j]) + 1 < len(words[i]):
					continue
				elif len(words[j]) + 1 > len(words[i]):
					break
				elif isNeighbor(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
			ans = max(ans, dp[i])
		return ans


class Solution:

	def can_convert(self, word1, word2):
		for missing_idx in range(len(word2)):
			if word2[:missing_idx] + word2[missing_idx + 1:] == word1:
				return True
		return False

	def longestStrChain(self, words: List[str]) -> int:
		words_by_length = collections.defaultdict(list)
		for (idx, word) in enumerate(words):
			words_by_length[len(word)].append(idx)
		adj_list = collections.defaultdict(list)
		indegree = [0] * len(words)
		for length in words_by_length:
			if length + 1 in words_by_length:
				for word_1_idx in words_by_length[length]:
					for word_2_idx in words_by_length[length + 1]:
						if self.can_convert(words[word_1_idx], words[word_2_idx]):
							adj_list[word_1_idx].append(word_2_idx)
							indegree[word_2_idx] += 1
		queue = collections.deque([word_idx for word_idx in range(len(words)) if indegree[word_idx] == 0])
		max_length = 0
		while queue:
			length = len(queue)
			max_length += 1
			for i in range(length):
				curr_word_idx = queue.popleft()
				for successor in adj_list[curr_word_idx]:
					indegree[successor] -= 1
					if indegree[successor] == 0:
						queue.append(successor)
		return max_length


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		d = dict()
		for word in words:
			d[word] = 1
		longest = 1
		for word in sorted(words, key=len):
			for i in range(len(word)):
				prev = word[:i] + word[i + 1:]
				if prev in d:
					d[word] = max(d[word], d[prev] + 1)
			longest = max(longest, d[word])
		return longest


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		lengths = [len(word) for word in words]
		wordsSorted = [x for (_, x) in sorted(zip(lengths, words), reverse=True)]
		print(wordsSorted)
		L = [1] * len(wordsSorted)
		maxLength = max(lengths)
		for k in range(0, len(L)):
			lenWord = len(wordsSorted[k])
			if lenWord == maxLength:
				L[k] = 1
			else:
				for l in range(k):
					if len(wordsSorted[l]) == lenWord + 1 and set(wordsSorted[l]) & set(wordsSorted[k]) == set(wordsSorted[k]):
						L[k] = max(L[k], 1 + L[l])
		return max(L)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = {}
		cnt = [[] for i in range(16)]
		min_l = 16
		for i in words:
			min_l = min([min_l, len(i)])
			cnt[len(i) - 1].append(i)

		def match(a, b):
			i = j = 0
			cnt = 0
			while j < len(b):
				if i < len(a) and a[i] == b[j]:
					i += 1
					j += 1
				else:
					j += 1
					cnt += 1
			return cnt == 1

		def topdown(curr_words):
			if len(curr_words) == 16:
				return 1
			if curr_words in dp:
				return dp[curr_words]
			dp[curr_words] = 1
			for i in cnt[len(curr_words)]:
				if match(curr_words, i):
					if not i in dp:
						dp[i] = topdown(i) + 1
					dp[curr_words] = max([dp[curr_words], dp[i]])
			return dp[curr_words]
		ans = 0
		for i in range(min_l - 1, 16):
			for j in cnt[i]:
				if j in dp:
					ans = max([ans, dp[j]])
				else:
					ans = max([ans, topdown(j)])
		return ans


from collections import deque

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		return self.run_graph_solution(words)

	def run_dp_solution(self, words):
		pass

	def run_graph_solution(self, words):
		graph = {word: [] for word in words}
		lengths = {k: [] for k in range(1, 17)}
		into = {}
		min_len = 17
		max_len = 1
		for word in words:
			lengths[len(word)].append(word)
			min_len = min(len(word), min_len)
			max_len = max(len(word), max_len)
		for k in range(min_len, max_len):
			for word1 in lengths[k]:
				for word2 in lengths[k + 1]:
					for i in range(len(word2)):
						if word2[:i] + word2[i + 1:] == word1:
							graph[word1].append(word2)
							into[word2] = True
		sources = [word for word in words if word not in into]
		max_len = 0
		for s in sources:
			max_len = max(max_len, self.run_bfs(s, graph))
		return max_len

	def run_bfs(self, s, graph):
		queue = deque(maxlen=len(list(graph.keys())))
		queue.appendleft((s, 1))
		summary = []
		while len(queue) > 0:
			(current_node, cur_len) = queue.pop()
			for word in graph[current_node]:
				queue.appendleft((word, cur_len + 1))
			summary.append(cur_len)
		return summary[-1]


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words_len = [[] for _ in range(16)]
		graph = {word: [] for word in words}
		for word in words:
			words_len[len(word) - 1].append(word)

		def predecessor(word1, word2):
			for i in range(len(word2)):
				if word2[:i] + word2[i + 1:] == word1:
					return True
			return False
		for i in range(len(words_len) - 1):
			words_1 = words_len[i]
			words_2 = words_len[i + 1]
			for word1 in words_1:
				for word2 in words_2:
					if predecessor(word1, word2):
						graph[word1].append(word2)
		memo = {word: -1 for word in words}

		def dfs(word):
			t = 1
			if memo[word] == -1:
				for w in graph[word]:
					t = max(t, 1 + dfs(w))
				memo[word] = t
			return memo[word]
		lpl = 0
		for words in words_len:
			for word in words:
				lpl = max(lpl, dfs(word))
		return lpl


from collections import defaultdict

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		chain = defaultdict(list)

		def checkPredecessor(w1, w2):
			for i in range(len(w2)):
				if w2[:i] + w2[i + 1:] == w1:
					return True
			return False
		for (idx, word) in enumerate(words):
			chain[len(word)].append((word, idx))
		dp = [0] * len(words)
		i = 1
		while i < 17:
			for (word, dp_idx) in chain[i]:
				if i - 1 in chain:
					for (checkWord, dp_jdx) in chain[i - 1]:
						if checkPredecessor(checkWord, word):
							dp[dp_idx] = max(dp[dp_idx], 1 + dp[dp_jdx])
			i += 1
		return max(dp) + 1


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def check(i, j):
			w1 = words[i]
			w2 = words[j]
			for k in range(len(w2)):
				if w1 == w2[:k] + w2[k + 1:]:
					return True
			return False
		buckets = defaultdict(list)
		for (i, word) in enumerate(words):
			l = len(word)
			buckets[l] += [i]
		g = defaultdict(list)
		for key in buckets:
			if key + 1 in buckets:
				for i in buckets[key]:
					for j in buckets[key + 1]:
						if check(i, j):
							g[i] += [j]
		ans = 0
		seen = set()
		for key in sorted(buckets.keys()):
			for i in buckets[key]:
				stack = [[1, i]]
				while stack:
					(level, node) = stack.pop()
					ans = max(ans, level)
					if node in seen:
						continue
					seen.add(node)
					if node in g:
						for child in g[node]:
							if child not in seen:
								stack += [[level + 1, child]]
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = {}
		result = 1
		for word in sorted(words, key=len):
			dp[word] = 1
			for i in range(len(word)):
				prev = word[:i] + word[i + 1:]
				if prev in dp:
					dp[word] = max(dp[word], dp[prev] + 1)
					result = max(result, dp[word])
		return result


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		lengthMap = {}
		for word in words:
			n = len(word)
			if n not in lengthMap:
				lengthMap[n] = []
			lengthMap[n].append(word)
		arr = [0 for i in range(len(words))]
		dp = {i: -1 for i in words}
		res = 1
		for i in range(len(words)):
			arr[i] = self.get_longest(dp, lengthMap, words[i])
			res = max(arr[i], res)
		print(arr)
		return res

	def get_longest(self, dp, lengthMap, word):
		if dp[word] != -1:
			return dp[word]
		if len(word) + 1 not in lengthMap:
			return 1
		res = 0
		for item in lengthMap[len(word) + 1]:
			if self.only_one_diff(word, item):
				res = max(res, self.get_longest(dp, lengthMap, item))
		dp[word] = res + 1
		return res + 1

	def only_one_diff(self, word1, word2):
		for i in range(len(word2)):
			if word2[:i] + word2[i + 1:] == word1:
				return True
		return False


class Solution:

	def longestStrChain(self, words):
		if not words:
			return 0
		wordTable = self.buildWordTable(words)
		maxLen = 0
		visited = set()
		for wordLen in range(min(wordTable), max(wordTable) + 1):
			for word in wordTable[wordLen]:
				if word not in visited:
					maxLen = max(maxLen, self.dfs(wordTable, word, visited))
		return maxLen

	def buildWordTable(self, words):
		wordTable = {}
		for word in words:
			if len(word) not in wordTable:
				wordTable[len(word)] = []
			wordTable[len(word)].append(word)
		return wordTable

	def dfs(self, wordTable, word, visited):
		maxLen = 0
		visited.add(word)
		if len(word) + 1 in wordTable:
			for neighbor in wordTable[len(word) + 1]:
				if self.isAncestor(word, neighbor):
					maxLen = max(maxLen, self.dfs(wordTable, neighbor, visited))
		return maxLen + 1

	def isAncestor(self, ancestor, successor):
		if len(ancestor) + 1 != len(successor):
			return False
		(i, j) = (0, 0)
		while i < len(ancestor) and j < len(successor):
			if ancestor[i] != successor[j]:
				j += 1
				continue
			else:
				i += 1
				j += 1
		return i == j or i == j - 1


class Solution:

	def isChild(self, parent, possible_child):
		for i in range(len(possible_child)):
			if possible_child[:i] + possible_child[i + 1:] == parent:
				return True
		return False

	def longestStrChain(self, words: List[str]) -> int:
		graph = {}
		word_lens = [[] for _ in range(17)]
		for w in words:
			graph[w] = []
			word_lens[len(w)].append(w)
		for i in range(1, 16):
			parents = word_lens[i]
			possible_children = word_lens[i + 1]
			for p in parents:
				for c in possible_children:
					if self.isChild(p, c):
						graph[p].append(c)
		longest_len = 0
		visited = {}
		sorted_keys = sorted(graph.keys())
		for node in sorted_keys:
			to_visit = [(node, 1)]
			while len(to_visit) != 0:
				(cur_node, depth) = to_visit.pop()
				visited[cur_node] = depth
				longest_len = max(depth, longest_len)
				for child in graph[cur_node]:
					if child not in visited:
						to_visit.append((child, depth + 1))
					elif depth + 1 > visited[child]:
						to_visit.append((child, depth + 1))
		return longest_len


from collections import deque

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		return self.run_graph_solution(words)

	def run_dp_solution(self, words):
		mem = {}

		def inner(w):
			if w in mem or len(w) == 0:
				return
			max_per_w = 0
			for j in range(len(w)):
				cur = w[:j] + w[j + 1:]
				if cur in mem:
					val = mem[cur] + 1
				else:
					val = inner(cur) + 1
				if val > max_per_w:
					max_per_w = val
			mem[w] = max_per_w
			return
		return max(mem.values())

	def run_graph_solution(self, words):
		graph = {word: [] for word in words}
		lengths = {k: [] for k in range(1, 17)}
		into = {}
		min_len = 17
		max_len = 1
		for word in words:
			lengths[len(word)].append(word)
			min_len = min(len(word), min_len)
			max_len = max(len(word), max_len)
		for k in range(min_len, max_len):
			for word1 in lengths[k]:
				for word2 in lengths[k + 1]:
					for i in range(len(word2)):
						if word2[:i] + word2[i + 1:] == word1:
							graph[word1].append(word2)
							into[word2] = True
		sources = [word for word in words if word not in into]
		max_len = 0
		for s in sources:
			max_len = max(max_len, self.run_bfs(s, graph))
		return max_len

	def run_bfs(self, s, graph):
		queue = deque(maxlen=len(list(graph.keys())))
		queue.appendleft((s, 1))
		summary = []
		while len(queue) > 0:
			(current_node, cur_len) = queue.pop()
			for word in graph[current_node]:
				queue.appendleft((word, cur_len + 1))
			summary.append(cur_len)
		return summary[-1]


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		print(words)
		if not words:
			return 0
		max_chain_dp = {}
		max_len = 1
		for i in range(len(words)):
			word_len = len(words[i])
			max_chain_dp[words[i]] = 1
			for j in range(i - 1, -1, -1):
				if len(words[j]) == word_len:
					continue
				elif len(words[j]) + 1 == word_len:
					if self.isChain(words[j], words[i]):
						max_chain_dp[words[i]] = max(1 + max_chain_dp[words[j]], max_chain_dp[words[i]])
						max_len = max(max_chain_dp[words[i]], max_len)
				else:
					break
		return max_len

	def isChain(self, word1, word2):
		if len(word2) - len(word1) > 1:
			return False
		added = False
		(i, j) = (0, 0)
		while i < len(word1) or j < len(word2):
			if i < len(word1) and word1[i] == word2[j]:
				i += 1
				j += 1
			elif added:
				return False
			else:
				j += 1
				added = True
		if i == len(word1) and j == len(word2):
			return True


class Solution:

	def isPredecessor(self, word1, word2):
		for i in range(1, len(word2) + 1):
			if word2[:i - 1] + word2[i:] == word1:
				return True
		return False

	def longestStrChain(self, words: List[str]) -> int:
		wordLengths = {}
		for word in words:
			if len(word) in wordLengths:
				wordLengths[len(word)].append(word)
			else:
				wordLengths[len(word)] = [word]
		longestStrChains = {}
		totalMaxLength = 1
		for length in sorted(wordLengths.keys()):
			for word in wordLengths[length]:
				if len(word) - 1 not in wordLengths:
					longestStrChains[word] = 1
				else:
					maxLength = 1
					for smallerWord in wordLengths[len(word) - 1]:
						if self.isPredecessor(smallerWord, word):
							if maxLength < longestStrChains[smallerWord] + 1:
								maxLength = longestStrChains[smallerWord] + 1
					longestStrChains[word] = maxLength
					if totalMaxLength < maxLength:
						totalMaxLength = maxLength
		print(wordLengths)
		print(longestStrChains)
		return totalMaxLength


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return
		dic = {}
		result = 1
		for word in sorted(words, key=len):
			dic[word] = 1
			for i in range(len(word)):
				currWord = word[:i] + word[i + 1:]
				if currWord in dic:
					dic[word] = max(dic[word], dic[currWord] + 1)
					result = max(result, dic[word])
		return result


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def dfs(w1, size):
			return max([dfs(w2, size + 1) for w2 in graph[w1]], default=size)
		graph = collections.defaultdict(list)
		for w in words:
			graph[len(w)].append(w)
		for w1 in words:
			for w2 in graph[len(w1) + 1]:
				for i in range(len(w2)):
					if w2[:i] + w2[i + 1:] == w1:
						graph[w1].append(w2)
		return max((dfs(w, 1) for w in words))


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		graph = collections.defaultdict(list)
		maxlen = float('-inf')
		minlen = float('inf')
		for word in words:
			graph[len(word)].append(word)
			maxlen = max(maxlen, len(word))
			minlen = min(minlen, len(word))
		memo = {}

		def predecessor(word1, word2):
			if not word1:
				return True
			if len(word1) + 1 != len(word2):
				return False
			if (word1, word2) in memo:
				return memo[word1, word2]
			fill = 1
			(left, right) = (0, 0)
			ans = True
			while left < len(word1) and right < len(word2):
				if word1[left] != word2[right]:
					if fill:
						right += 1
						fill -= 1
						continue
					else:
						ans = False
						break
				left += 1
				right += 1
			memo[word1, word2] = ans
			return ans

		def chain(length, s=''):
			if length not in graph:
				return 0
			ans = 0
			for w in graph[length]:
				if predecessor(s, w):
					ans = max(ans, 1 + chain(length + 1, w))
			return ans
		return max((chain(l) for l in range(minlen, maxlen + 1)))


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		dp = [1] * len(words)
		possible_pred = [0] * len(words)
		for i in range(len(words) - 1, -1, -1):
			cur_word = words[i]
			cur_length = len(cur_word)
			for j in range(i + 1, len(words)):
				if len(words[j]) == cur_length + 1 and cur_word in possible_pred[j]:
					dp[i] = max(dp[i], dp[j] + 1)
			pred = set()
			for k in range(len(cur_word)):
				pred.add(cur_word[0:k] + cur_word[k + 1:])
			possible_pred[i] = pred
		return max(dp)


class Solution:

	def checkPredecessor(self, word_1, word_2):
		find_extra = False
		for i in range(len(word_1)):
			chr_1 = word_1[i]
			if not find_extra:
				chr_2 = word_2[i]
			else:
				chr_2 = word_2[i + 1]
			if chr_1 != chr_2:
				if find_extra:
					return False
				else:
					if chr_1 != word_2[i + 1]:
						return False
					find_extra = True
		return True

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		longest_seq = [1] * len(words)
		for i in range(1, len(words)):
			curr_word = words[i]
			for j in range(0, i)[::-1]:
				prev_word = words[j]
				if len(prev_word) == len(curr_word):
					continue
				if len(prev_word) + 1 < len(curr_word):
					break
				if self.checkPredecessor(prev_word, curr_word):
					longest_seq[i] = max(longest_seq[i], longest_seq[j] + 1)
		return max(longest_seq)


import collections

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		self.graph = collections.defaultdict(list)
		for word in words:
			self.graph[len(word)].append(word)
		for word1 in words:
			for word2 in self.graph[len(word1) + 1]:
				for i in range(len(word2)):
					if word2[:i] + word2[i + 1:] == word1:
						self.graph[word1].append(word2)
		return max((self.dfs(w, 1) for w in words))

	def dfs(self, word1, size):
		return max([self.dfs(word2, size + 1) for word2 in self.graph[word1]], default=size)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def isPredecessor(s1, s2):
			add = False
			s1_inx = 0
			s2_inx = 0
			while s1_inx < len(s1) and s2_inx < len(s2):
				if s1[s1_inx] == s2[s2_inx]:
					s1_inx += 1
					s2_inx += 1
				elif add == False:
					s2_inx += 1
					add = True
				else:
					return False
			return True
		words = sorted(words, key=lambda x: len(x))
		dp = [1] * len(words)
		res = 1
		for i in range(len(words)):
			for j in range(0, i):
				if len(words[i]) == len(words[j]):
					break
				elif len(words[i]) - 1 > len(words[j]):
					continue
				elif isPredecessor(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
					res = max(res, dp[i])
		return res


class Solution:

	def plusOne(self, a, b):
		bigger = max([a, b], key=len)
		smaller = min([a, b], key=len)
		for i in range(len(bigger)):
			if bigger[:i] + bigger[i + 1:] == smaller:
				return True
		return False

	def longestStrChain(self, words: List[str]) -> int:
		memo = {}
		sort = [[i for i in words if len(i) == a] for a in set([len(j) for j in words])][::-1]
		print(sort)
		for (i, row) in enumerate(sort):
			if i == 0:
				for j in row:
					memo[j] = 1
			else:
				for a in row:
					values = []
					for b in sort[i - 1]:
						if self.plusOne(a, b):
							print((a, b))
							values.append(1 + memo[b])
					memo[a] = max(values) if values else 1
		return max(memo.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		n = len(words)
		dp = [1] * n
		for i in range(n):
			for j in reversed(list(range(i))):
				if len(words[i]) == len(words[j]):
					continue
				elif len(words[i]) > len(words[j]) + 1:
					break
				if self.helper(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)

	def helper(self, w1, w2):
		i = 0
		while i < len(w1) and w1[i] == w2[i]:
			i += 1
		while i < len(w1) and w1[i] == w2[i + 1]:
			i += 1
		return i == len(w1)


from collections import defaultdict
from queue import Queue

class Solution:

	def is_pred(self, w1, w2):
		for i in range(len(w2)):
			if w2[:i] + w2[i + 1:] == w1:
				return True
		return False

	def longestStrChain(self, words: List[str]) -> int:
		graph = defaultdict(list)
		words_by_len = defaultdict(list)
		for word in words:
			n = len(word)
			words_by_len[n].append(word)
		roots = set(words)
		for word in words:
			possible_preds = words_by_len[len(word) - 1]
			for pred in possible_preds:
				if self.is_pred(pred, word):
					graph[pred].append(word)
					if word in roots:
						roots.remove(word)
		max_depth = 1
		for root in roots:
			q = Queue()
			q.put((root, 1))
			while not q.empty():
				(curr, depth) = q.get()
				max_depth = max(max_depth, depth)
				descs = graph[curr]
				for desc in descs:
					q.put((desc, depth + 1))
		return max_depth


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def predecessor(word1, word2):
			for i in range(len(word2)):
				if word2[0:i] + word2[i + 1:] == word1:
					return True
			return False
		words.sort(key=len)
		words_sort = {}
		for i in words:
			if len(i) in words_sort:
				words_sort[len(i)].append(i)
			else:
				words_sort[len(i)] = [i]

		def dfs(words, words_sort):
			max_chain = 1
			stack = [(1, word) for word in words[::-1]]
			while stack:
				current = stack.pop()
				if current[0] > max_chain:
					max_chain = current[0]
				if len(current[1]) + 1 in words_sort:
					for word in words_sort[len(current[1]) + 1]:
						if predecessor(current[1], word):
							if (1, word) in stack:
								stack.remove((1, word))
							stack.append((current[0] + 1, word))
				else:
					continue
			return max_chain
		max_chain = dfs(words, words_sort)
		return max_chain


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		m = collections.defaultdict(list)
		words = sorted(words, key=len)
		for w in words:
			m[len(w)].append(''.join(sorted(w)))
		if len(m) == 1:
			return 1

		def equal(x, y):
			for i in range(len(x)):
				if x[i] != y[i]:
					return x == y[:i] + y[i + 1:]
			return True

		def dfs(w):
			k = len(w) + 1
			if k not in m:
				return 0
			return max([dfs(x) + 1 for x in m[k] if equal(w, x)] or [0])
		return max((dfs(x) for y in list(m.keys())[:-1] for x in m[y])) + 1


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		counter = {}
		minLen = len(words[0])
		maxLen = 1
		for idx in range(len(words)):
			if len(words[idx]) == minLen:
				counter[idx] = 1
			else:
				ancestor = 1
				j = 0
				while idx - j >= 0 and len(words[idx - j]) >= len(words[idx]) - 1:
					j += 1
					if len(words[idx - j]) == len(words[idx]):
						continue
					if self.checker(words[idx - j], words[idx]):
						ancestor = max(ancestor, counter[idx - j] + 1)
				counter[idx] = ancestor
				maxLen = max(maxLen, ancestor)
		return maxLen

	def checker(self, short, long):
		for idx in range(len(long)):
			removed = long[0:idx] + long[idx + 1:]
			if short == removed:
				return True
		return False


class Solution:

	def IsPredecessor(self, w1, w2):
		if len(w1) + 1 != len(w2):
			return False
		if len(w1) == 0:
			return True
		diff = 0
		for i in range(len(w2)):
			if i - diff == len(w1) or w1[i - diff] != w2[i]:
				diff += 1
		return diff == 1

	def longestStrChain(self, words: List[str]) -> int:
		if len(words) < 1:
			return 0
		length_position = [[] for i in range(17)]
		for i in range(len(words)):
			w = words[i]
			length_position[len(w)].append(i)
		dp = [1] * len(words)
		for i in range(2, 17):
			if len(length_position[i - 1]) == 0 or len(length_position[i]) == 0:
				continue
			current = length_position[i]
			previous = length_position[i - 1]
			for j in current:
				for k in previous:
					if self.IsPredecessor(words[k], words[j]):
						dp[j] = max(dp[j], dp[k] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		size = 0
		wordSet = set(words)
		mem = {}

		def dfs(s):
			if s in mem:
				return mem[s]
			maxpath = 1
			for i in range(len(s)):
				new = s[:i] + s[i + 1:]
				if new in wordSet:
					maxpath = max(maxpath, 1 + dfs(new))
			mem[s] = maxpath
			return mem[s]
		for word in words:
			if word not in mem:
				size = max(size, dfs(word))
		print(mem)
		return size
		dic = collections.defaultdict(int)
		words = sorted(words, key=lambda x: len(x))
		for word in words:
			dic[word] = 1
			for i in range(len(word)):
				tmp = word[:i] + word[i + 1:]
				if tmp in dic:
					dic[word] = max(dic[word], dic[tmp] + 1)
		return max(dic.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		chains = {}
		len_arr = [len(x) for x in words]
		(min_len, max_len) = (min(len_arr), max(len_arr))
		max_len_w = [w for w in words if len(w) == max_len]
		for w in max_len_w:
			chains[w] = 1
		for length in range(max_len - 1, min_len - 1, -1):
			for w in words:
				if len(w) != length:
					continue
				max_w = 1
				for key in chains:
					if len(key) == len(w) + 1 and self.is_chain(w, key):
						max_w = max(max_w, chains[key] + 1)
				chains[w] = max_w
		len_chain = [y for (x, y) in list(chains.items())]
		return max(len_chain)

	def is_chain(self, small_w, large_w):
		for i in range(len(large_w)):
			if large_w[:i] + large_w[i + 1:] == small_w:
				return True
		return False


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = {}
		words_dict = {}
		for word in words:
			dp[word] = -1
			if words_dict.get(len(word)):
				words_dict[len(word)].append(word)
			else:
				words_dict[len(word)] = [word]
		result = 0
		for word in words:
			result = max(result, self.longest_chain(word, dp, words_dict))
		return result

	def longest_chain(self, word, dp, words_dict):
		if dp[word] != -1:
			return dp[word]
		if not words_dict.get(len(word) + 1):
			return 1
		res = 0
		for word2 in words_dict[len(word) + 1]:
			if self.isSucc(word, word2):
				res = max(res, self.longest_chain(word2, dp, words_dict))
		res += 1
		return res

	def isSucc(self, word1, word2):
		if len(word1) != len(word2) - 1:
			return False
		count = 0
		i = 0
		j = 0
		while i < len(word1):
			if word1[i] != word2[j]:
				if count == 1:
					return False
				count += 1
				j += 1
			else:
				j += 1
				i += 1
		return True


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		chainLen = {w: 1 for w in words}
		ret = 1
		for (i, word1) in enumerate(words):
			for j in range(i + 1, len(words)):
				word2 = words[j]
				if len(word2) == len(word1):
					continue
				if len(word2) > len(word1) + 1:
					break
				insert = False
				match = True
				idx1 = 0
				idx2 = 0
				while idx1 < len(word1):
					if word1[idx1] != word2[idx2]:
						if insert:
							match = False
							break
						else:
							insert = True
							idx2 += 1
							continue
					idx1 += 1
					idx2 += 1
				if match:
					l = max(chainLen[word2], chainLen[word1] + 1)
					ret = max(ret, l)
					chainLen[word2] = l
		return ret


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = {}
		table = defaultdict(list)
		for w in words:
			table[len(w)].append(w)
		max_len = max((len(w) for w in words))

		def backtracking(cur, n):
			if len(cur) == max_len:
				return 0
			if not cur in dp:
				res = 0
				for word in table[n]:
					for i in range(len(word)):
						if word[0:i] + word[i + 1:] == cur:
							res = max(res, backtracking(word, n + 1) + 1)
							break
				dp[cur] = res
			return dp[cur]
		res = 0
		for (i, v) in table.items():
			for w in v:
				res = max(res, backtracking(w, i + 1) + 1)
		return res


class Solution:

	def get_dict(self, word):
		d = {}
		for c in word:
			d[c] = d.get(c, 0) + 1
		return d

	def is_close(self, word1, word2):
		dict_word1 = self.get_dict(word1)
		dict_word2 = self.get_dict(word2)
		diff = False
		for (letter, freq) in list(dict_word2.items()):
			if letter in dict_word1:
				if abs(freq - dict_word1[letter]) == 1:
					if not diff:
						diff = True
					else:
						return False
				elif abs(freq - dict_word1[letter]) > 1:
					return False
			elif freq > 1:
				return False
			elif not diff:
				diff = True
			else:
				return False
		return True

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		dict_lens = {}
		dict_words = {}
		for word in words:
			dict_lens.setdefault(len(word), []).append(word)
			dict_words[word] = 0
		max_res = 0
		sorted_keys = sorted(dict_lens.keys())
		for len_num in sorted_keys:
			if len_num + 1 in dict_lens:
				next_word_list = dict_lens[len_num + 1]
			else:
				continue
			for word in dict_lens[len_num]:
				for next_word in next_word_list:
					if self.is_close(word, next_word):
						dict_words[next_word] = max(dict_words[next_word], dict_words[word] + 1)
						max_res = max(max_res, dict_words[next_word])
		return max_res + 1


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		contains = lambda w1, w2: all((l1 in w2 for l1 in w1))
		words.sort(key=lambda a: len(a))
		n = len(words)
		chain = [1] * n
		for i in range(n):
			j = i + 1
			while j < n and len(words[j]) == len(words[i]):
				j += 1
			while j < n and len(words[j]) == len(words[i]) + 1:
				if contains(words[i], words[j]) and chain[i] + 1 > chain[j]:
					chain[j] = chain[i] + 1
				j += 1
		return max(chain)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		d = {}
		for word in words:
			if len(word) in d:
				d[len(word)].append(word)
			else:
				d[len(word)] = [word]
		visited = {}
		res = 0
		for word in sorted(words):
			res = max(res, self.dfs(word, visited, d))
		return res

	def checkPredecessor(self, word1, word2):
		return any((word1 == word2[:i] + word2[i + 1:] for i in range(len(word2))))

	def dfs(self, word, visited, d):
		if word in visited:
			return visited[word]
		if len(word) + 1 not in d:
			visited[word] = 1
			return 1
		res = 1
		for w in d[len(word) + 1]:
			if self.checkPredecessor(word, w):
				res = max(res, self.dfs(w, visited, d) + 1)
		visited[word] = res
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		n = len(words)
		W = defaultdict(list)
		for (i, w) in enumerate(words):
			W[len(w)].append(i)
		G = defaultdict(set)
		for i in range(n):
			for j in W[len(words[i]) + 1]:
				found = False
				for k in range(len(words[j])):
					if words[i] == words[j][:k] + words[j][k + 1:]:
						found = True
						break
				if found:
					G[i].add(j)

		@lru_cache(None)
		def dfs(i):
			out = 1
			for j in G[i]:
				out = max(out, 1 + dfs(j))
			return out
		return max((dfs(i) for i in range(n)))


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dicti = collections.defaultdict(set)
		for word in words:
			dicti[len(word)].add(word)
		chars = [chr(i) for i in range(ord('a'), ord('z') + 1)]
		memo = {}

		def dist(word):
			if word in memo:
				return memo[word]
			if len(word) + 1 not in dicti:
				memo[word] = 1
				return memo[word]
			n = len(word)
			ans = 0
			for ch in chars:
				for i in range(n + 1):
					new_word = word[:i] + ch + word[i:]
					if new_word in dicti[n + 1]:
						ans = max(ans, dist(new_word))
			memo[word] = ans + 1
			return ans + 1
		ans = 0
		for word in words:
			ans = max(ans, dist(word))
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = [1 for _ in range(len(words) + 1)]
		dp[0] = 0
		words = sorted(words, key=lambda x: len(x))
		hmap = collections.defaultdict(list)
		for (i, word) in enumerate(words):
			hmap[len(word)] += [(word, i)]
		for i in range(1, len(words) + 1):
			key = len(words[i - 1]) - 1
			for (word, idx) in hmap[key]:
				if self.predecessor(word, words[i - 1]):
					dp[i] = max(dp[i], dp[idx + 1] + 1)
		return max(dp)

	def predecessor(self, word0, word1):
		cnt0 = collections.Counter(word0)
		cnt1 = collections.Counter(word1)
		for key in cnt0:
			if key not in cnt1:
				return False
		return True


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if len(words) <= 0:
			return 0
		words.sort(key=len)
		numberOfWords = len(words)
		longestLens = [1] * len(words)
		index = numberOfWords - 1
		while index >= 0:
			if index == 0 or len(words[index]) != len(words[index - 1]):
				index -= 1
				break
			index -= 1
		while index >= 0:
			maxLen = 1
			index2 = index + 1
			while index2 < numberOfWords and len(words[index]) + 1 >= len(words[index2]):
				if self.isPredecessor(words[index], words[index2]):
					if maxLen < longestLens[index2] + 1:
						maxLen = longestLens[index2] + 1
				index2 += 1
			longestLens[index] = maxLen
			index -= 1
		maxLen = longestLens[0]
		for longestLen in longestLens:
			if maxLen < longestLen:
				maxLen = longestLen
		return maxLen

	def isPredecessor(self, word1: str, word2: str) -> bool:
		if len(word2) - len(word1) != 1:
			return False
		for (i, ch) in enumerate(word2):
			newWord = word2[:i] + word2[i + 1:]
			if newWord == word1:
				return True
		return False


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = {}
		for w in sorted(words, key=len):
			dp[w] = max((dp.get(w[:i] + w[i + 1:], 0) + 1 for i in range(len(w))))
		return max(dp.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		n = len(words)
		a = sorted(words, key=len)
		dp = [1] * n

		def helper(a1, b1):
			s = 0
			n = len(b1)
			i = 0
			j = 0
			while i < n and j < n + 1:
				if a1[j] == b1[i]:
					i += 1
					j += 1
				elif a1[j] != b1[i] and s == 0:
					s += 1
					j += 1
				else:
					return 0
			return 1
		for i in range(1, n):
			for j in range(i - 1, -1, -1):
				if len(a[j]) == len(a[i]):
					continue
				elif len(a[j]) < len(a[i]) - 1:
					break
				x = helper(a[i], a[j])
				if x == 1:
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		from collections import defaultdict
		d = {}
		for word in words:
			if len(word) in d:
				d[len(word)].append(word)
			else:
				d[len(word)] = [word]

		def isPred(w1, w2):
			for i in range(len(w2)):
				if w2[:i] + w2[i + 1:] == w1:
					return True
			return False
		followers = defaultdict(list)
		for word in words:
			if len(word) + 1 in d:
				for biggerWord in d[len(word) + 1]:
					if isPred(word, biggerWord):
						followers[word].append(biggerWord)
		self.maxDist = 1

		def dfs(start, dist, found=set()):
			found.add(start)
			for neighbor in followers[start]:
				if neighbor not in found:
					self.maxDist = max(self.maxDist, dist + 1)
					dfs(neighbor, dist + 1, found)
		keys = [key for key in followers]
		for key in keys:
			s = set()
			dfs(key, 1, set())
		return self.maxDist


class Solution:

	def isPredecessor(self, prev_word, cur_word):
		if len(prev_word) != len(cur_word) - 1:
			return False
		skipped_char = False
		for i in range(len(prev_word)):
			if not skipped_char and prev_word[i] != cur_word[i]:
				skipped_char = True
			if skipped_char and prev_word[i] != cur_word[i + 1]:
				return False
		return True

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda word: len(word))
		num_words = len(words)
		chain_lengths = [1 for _ in range(num_words)]
		max_chain_length = 0
		for i in range(num_words):
			for j in range(0, i):
				if len(words[j]) == len(words[i]) - 1 and chain_lengths[j] + 1 > chain_lengths[i] and self.isPredecessor(words[j], words[i]):
					chain_lengths[i] = chain_lengths[j] + 1
			max_chain_length = max(max_chain_length, chain_lengths[i])
		return max_chain_length


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def isPred(w1, w2):
			(i, j) = (0, 0)
			while i < len(w1):
				if w1[i] != w2[j]:
					if j != i:
						return False
					j += 1
				else:
					j += 1
					i += 1
			return True
		words = sorted(words, key=lambda x: len(x))
		dp = [1] * len(words)
		for i in range(1, len(words)):
			for j in range(i):
				if len(words[i]) == len(words[j]) + 1 and isPred(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		n = len(words)
		for ele in words:
			ele = list(ele)
		words = sorted(words, key=lambda x: len(x))
		arr = [1] * n
		for i in range(1, n):
			for j in range(0, i):
				if len(words[j]) == len(words[i]) - 1:
					if all((x in words[i] for x in words[j])):
						arr[i] = max(arr[i], arr[j] + 1)
		print(arr)
		return max(arr)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		auxList = [(len(item), item) for item in set(words)]
		auxList.sort()
		auxCntList = [1] * len(auxList)
		ans = 1
		for (idx, (wordLen, word)) in enumerate(auxList):
			for jdx in range(idx + 1, len(auxList)):
				(cWordLen, cWord) = auxList[jdx]
				if cWordLen > wordLen + 1:
					break
				elif cWordLen == wordLen:
					pass
				else:
					for pivot in range(len(cWord)):
						if cWord[:pivot] + cWord[pivot + 1:] == word:
							auxCntList[jdx] = auxCntList[idx] + 1
							ans = max(ans, auxCntList[jdx])
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		wordsbylen = collections.defaultdict(list)
		for w in words:
			wordsbylen[len(w)].append(w)

		def get_longest_derivate(word):
			potential = wordsbylen[len(word) + 1]
			possible = [1]
			for p in potential:
				(i, j) = (0, 0)
				while i < len(p) and j < len(word):
					if p[i] == word[j]:
						i += 1
						j += 1
					elif i != j:
						break
					else:
						i += 1
				if j == len(word):
					possible.append(1 + get_longest_derivate(p))
			return max(possible)
		return max(map(get_longest_derivate, words))


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		auxList = [(len(item), item) for item in set(words)]
		auxList.sort()
		auxGraph = collections.defaultdict(set)
		seen = dict()
		for (idx, (wordLen, word)) in enumerate(auxList):
			seen[word] = False
			for jdx in range(idx + 1, len(auxList)):
				(cWordLen, cWord) = auxList[jdx]
				if cWordLen > wordLen + 1:
					break
				elif cWordLen == wordLen:
					pass
				else:
					for pivot in range(len(cWord)):
						if cWord[:pivot] + cWord[pivot + 1:] == word:
							auxGraph[word].add(cWord)
		ans = 0
		auxDeque = collections.deque()
		for (_, word) in auxList:
			if seen[word]:
				pass
			else:
				seen[word] = True
				auxDeque.append((1, word))
				while len(auxDeque) > 0:
					(cLen, cnode) = auxDeque.pop()
					ans = max(ans, cLen)
					for eachNeighbor in auxGraph[cnode]:
						if not seen[eachNeighbor]:
							seen[eachNeighbor] = True
							auxDeque.append((cLen + 1, eachNeighbor))
		return ans


from collections import Counter, defaultdict

class Solution:

	def is_one_away(self, c_1, c_2) -> bool:
		diff = 0
		for (k, v) in list(c_2.items()):
			diff += v - c_1.get(k, 0)
			if diff > 1:
				return False
		for k in c_1:
			if k not in c_2:
				return False
		return True

	def helper(self, word, words_for_len, counters_for_words):
		w_counter = counters_for_words[word]
		max_chain = 0
		for w in words_for_len[len(word) + 1]:
			if self.is_one_away(w_counter, counters_for_words[w]):
				max_chain = max(max_chain, self.helper(w, words_for_len, counters_for_words))
		return max_chain + 1

	def longestStrChain(self, words: List[str]) -> int:
		words_for_len = defaultdict(list)
		counters_for_words = {w: Counter(w) for w in words}
		for w in words:
			words_for_len[len(w)].append(w)
		max_chain = 0
		for w in words:
			max_chain = max(max_chain, self.helper(w, words_for_len, counters_for_words))
		return max_chain


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def is_predecessor(w1, w2):
			for (i, w) in enumerate(w1):
				if w != w2[i]:
					return w1[i:] == w2[i + 1:]
			return True
		words.sort(key=len, reverse=True)
		len_words = len(words)
		combos = [0] * len_words
		for i in range(len_words):
			for j in reversed(list(range(0, i))):
				(len_i, len_j) = (len(words[i]), len(words[j]))
				if len_i + 1 < len_j:
					break
				elif len_i == len_j:
					continue
				if combos[i] < combos[j] + 1 and is_predecessor(words[i], words[j]):
					combos[i] = combos[j] + 1
		return max(combos) + 1


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		dp = [1] * len(words)
		m = 1
		for i in range(1, len(words)):
			j = i - 1
			cl = len(words[i])
			while len(words[j]) >= cl - 1 and j > -1:
				if len(words[j]) == cl:
					j -= 1
					continue
				f = 0
				(w1, w2) = (words[i], words[j])
				(li, lj) = (0, 0)
				while f < 2 and lj < len(w2):
					if w1[li] == w2[lj]:
						li += 1
						lj += 1
					else:
						f += 1
						li += 1
				if f != 2:
					dp[i] = max(dp[i], 1 + dp[j])
					m = max(dp[i], m)
				j -= 1
		return m


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def check(str1, str2):
			for i in range(len(str2)):
				temp = str2[:i] + str2[i + 1:]
				if temp == str1:
					return True
			return False
		words.sort(key=len)
		min_length = len(words[0])
		dp = [1] * len(words)
		for i in range(len(words)):
			if len(words[i]) == min_length:
				continue
			for j in range(len(words)):
				if len(words[j]) == len(words[i]) - 1:
					if check(words[j], words[i]):
						dp[i] = max(dp[i], dp[j] + 1)
				elif len(words[j]) >= len(words[i]):
					break
		return max(dp)


def is_pre(s1, s2):
	c = 0
	i = 0
	for j in range(len(s2)):
		if i == len(s1) or s1[i] != s2[j]:
			c += 1
		else:
			i += 1
	return c == 1

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		n = len(words)
		m = {}
		incount = {}
		q = collections.deque()
		seen = set()
		for i in range(n):
			if i not in incount:
				q.append(i)
			wn = len(words[i])
			for j in range(i + 1, n):
				jn = len(words[j])
				if jn > wn + 1:
					break
				if jn == wn + 1 and is_pre(words[i], words[j]):
					m.setdefault(i, []).append(j)
					incount[j] = incount.get(j, 0) + 1
		lev = 0
		while q:
			lev += 1
			for i in range(len(q)):
				u = q.popleft()
				for v in m.get(u, []):
					if v not in seen:
						q.append(v)
						seen.add(v)
		return lev


def is_pred(w1, w2):
	skip_count = 0
	if len(w1) + 1 != len(w2):
		return False
	for i in range(0, len(w1)):
		if w1[i] == w2[i + skip_count]:
			pass
		elif skip_count == 0 and w1[i] == w2[i + 1]:
			skip_count += 1
		else:
			return False
	return True

def tests():
	assert is_pred('a', 'ab')
	assert not is_pred('a', 'a')
	assert not is_pred('a', 'bc')
	assert not is_pred('ab', 'a')

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda w: len(w))
		chains = {}
		current_max = 0
		for w in words:
			chains[w] = 1
			current_max = max(current_max, 1)
			for (chain, chain_len) in list(chains.items()):
				if is_pred(chain, w):
					chains[w] = max(chains[w], chain_len + 1)
					current_max = max(current_max, chains[w])
		return current_max


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def is_predecessor(w1, w2):
			for i in range(len(w1)):
				if w1[i] != w2[i]:
					return w1[i:] == w2[i + 1:]
			return True
		words.sort(key=len, reverse=True)
		len_words = len(words)
		combos = [0] * len_words
		for i in range(len_words):
			for j in range(0, i):
				if len(words[i]) + 1 == len(words[j]) and combos[i] < combos[j] + 1 and is_predecessor(words[i], words[j]):
					combos[i] = combos[j] + 1
		return max(combos) + 1


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		dp = [1 for i in range(len(words))]
		for r in range(1, len(words)):
			for l in range(r):
				if len(words[r]) == len(words[l]) + 1:
					missingLetters = i = 0
					for j in range(len(words[r])):
						if i >= len(words[l]) or words[l][i] != words[r][j]:
							missingLetters += 1
							if missingLetters > 1:
								break
						else:
							i += 1
					if missingLetters == 1:
						dp[r] = max(dp[r], dp[l] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		words = sorted(words, key=len)
		map = {}
		DP = [1 for idx in range(len(words))]
		for i in range(len(words)):
			map = {}
			for j in range(0, i):
				if len(words[i]) == len(words[j]) + 1:
					diff = 0
					for comp in range(len(words[i])):
						if diff == 0 and comp == len(words[i]) - 1:
							diff = 1
							continue
						if words[i][comp] == words[j][comp - diff]:
							continue
						elif diff == 1:
							diff = 69
							break
						else:
							diff = 1
					if diff == 1:
						if DP[j] + 1 > DP[i]:
							DP[i] = DP[j] + 1
		return max(DP)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def is_predecessor(w1, w2):
			skip = 0
			for i in range(len(w2)):
				j = i - skip
				if j == len(w1):
					break
				if w1[j] != w2[i]:
					skip += 1
					if skip >= 2:
						return False
			return True
		words.sort(key=len, reverse=True)
		len_words = len(words)
		combos = [0] * len_words
		for i in range(len_words):
			for j in range(0, i):
				if len(words[i]) + 1 == len(words[j]) and combos[i] < combos[j] + 1 and is_predecessor(words[i], words[j]):
					combos[i] = combos[j] + 1
		for i in range(len_words):
			print(combos[i], end=', ')
			print(words[i])
		return max(combos) + 1


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		words = sorted(words, key=lambda x: len(x))
		dp = [1] * len(words)
		for i in range(1, len(words)):
			for j in range(i - 1, -1, -1):
				if len(words[i]) == len(words[j]) + 1:
					update = True
					for c in words[j]:
						if c not in words[i]:
							update = False
					if update:
						dp[i] = max(dp[i], 1 + dp[j])
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		n = len(words)
		dp = [1] * n
		for i in range(1, n):
			word = words[i]
			word_len = len(word)
			for j in range(0, i):
				if len(words[j]) == word_len - 1:
					flag = False
					for t in range(word_len):
						if word[:t] + word[t + 1:] == words[j]:
							flag = True
					if flag:
						dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def check(s, t):
			(m, n) = (len(s), len(t))
			flag = False
			j = 0
			if n != m + 1:
				return False
			for i in range(n):
				if j < m and t[i] == s[j]:
					j += 1
				elif not flag:
					flag = True
				else:
					return False
			return True
		words = sorted(words, key=lambda entry: len(entry), reverse=False)
		table = [1] * len(words)
		for i in range(1, len(table)):
			maxVal = 0
			for j in range(i):
				if len(words[j]) + 1 == len(words[i]) and check(words[j], words[i]) and (table[i] < table[j] + 1):
					table[i] = table[j] + 1
		return max(table)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		words = sorted(words, key=lambda x: len(x))
		print(words)

		def valid(word1, word2):
			i = 0
			j = 0
			flag = False
			while i < len(word1) and j < len(word2):
				if word1[i] == word2[j]:
					i += 1
					j += 1
					continue
				if not flag and word1[i] != word2[j]:
					flag = True
					j += 1
					continue
				if flag and word1[i] != word2[j]:
					return False
			return i == len(word1)
		res = 1
		dp = [1] * len(words)
		for i in range(1, len(words)):
			for j in range(i):
				if len(words[j]) + 1 == len(words[i]) and valid(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
			res = max(res, dp[i])
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def ispre(w1, w2):
			(i, j) = (0, 0)
			while i < len(w1) and j < len(w2):
				if w1[i] == w2[j]:
					i += 1
					j += 1
				else:
					j += 1
			return i == len(w1)
		words.sort(key=len)
		dp = [0] * len(words)

		def dfs(i):
			if dp[i] != 0:
				return dp[i]
			dp[i] = 1
			for j in range(i, len(words)):
				if len(words[j]) <= len(words[i]):
					continue
				if len(words[j]) > len(words[i]) + 1:
					break
				if ispre(words[i], words[j]):
					dp[i] = max(dp[i], 1 + dfs(j))
			return dp[i]
		ans = max((dfs(i) for i in range(len(words))))
		return ans


class Solution:

	def is_chainable(self, shorter, longer):
		for i in range(len(longer)):
			if shorter == longer[:i] + longer[i + 1:]:
				return True
		return False

	def longestStrChain(self, words: List[str]) -> int:
		sw = sorted(words, key=lambda x: len(x))
		n_words = len(sw)
		chains = [1] * n_words
		out = 1
		for i in range(n_words):
			word = sw[i]
			for j in range(i + 1, n_words):
				next_word = sw[j]
				if len(word) == len(next_word):
					continue
				elif len(word) - len(next_word) != -1:
					break
				if self.is_chainable(word, next_word):
					chains[j] = chains[i] + 1
					out = max(out, chains[j])
		return out


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if len(words) == 0:
			return 0

		def isRelate(small: str, big: str) -> bool:
			for i in range(len(big)):
				if small == big[:i] + big[i + 1:]:
					return True
			return False

		def lengthList(target: int) -> List[str]:
			if target == 0:
				return []
			final = []
			for i in words:
				if len(i) == target:
					final.append(i)
			return final
		dp = collections.defaultdict(int)
		words.sort(key=lambda x: len(x))
		for word in words:
			compareList = lengthList(len(word) - 1)
			maxx = 0
			if len(compareList) == 0:
				dp[word] = 1
			else:
				for small in compareList:
					if isRelate(small, word):
						maxx = max(maxx, dp[small])
				dp[word] = maxx + 1
		return max(dp.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		word_list = sorted(words, key=lambda x: len(x))
		word_dict = {word: 1 for word in word_list}
		longest = 0
		for word in word_list:
			for i in range(len(word)):
				test = word[:i] + word[i + 1:]
				if test in word_dict:
					word_dict[word] = word_dict[test] + 1
				longest = max(longest, word_dict[word])
		return longest


from collections import Counter

class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def in_c(a: int, b: int):
			for (k, v) in list(a.items()):
				if k not in b or b[k] < v:
					return False
			return True
		N = len(words)
		words = sorted(words, key=lambda i: len(i))
		word_c = [Counter(ii) for ii in words]
		dp = [1] * N
		for ii in range(N):
			can = [kk for (jj, kk, mm) in zip(word_c[:ii], dp[:ii], words[:ii]) if len(words[ii]) == len(mm) + 1 and in_c(jj, word_c[ii])]
			if can:
				dp[ii] = max(can) + 1
		print(words)
		print(dp)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda w: len(w))

		def predecessor(a: str, b: str):
			if len(b) - len(a) == 1:
				mismatch = 0
				(a_idx, b_idx) = (0, 0)
				while a_idx < len(a) and mismatch <= 1:
					if a[a_idx] != b[b_idx]:
						mismatch += 1
						b_idx += 1
					else:
						a_idx = a_idx + 1
						b_idx = b_idx + 1
				if mismatch == 1 or not mismatch:
					return True
			return False
		dp = [1]
		for word in words[1:]:
			max_length = 1
			for i in range(len(dp)):
				if predecessor(words[i], word):
					max_length = max(max_length, dp[i] + 1)
			dp.append(max_length)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = [1 for i in range(len(words))]
		words.sort(key=lambda x: len(x))
		for i in range(len(words)):
			for j in range(i):
				if len(words[j]) == len(words[i]):
					continue
				if len(words[i]) - len(words[j]) > 1:
					continue
				else:
					count = 0
					for ch in words[j]:
						if ch in words[i]:
							count += 1
					if count == len(words[j]):
						dp[i] = dp[j] + 1
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def connected(x, y):
			(i, j) = (0, 0)
			count = 0
			while i < len(y) and j < len(x):
				if y[i] != x[j]:
					if count == 0:
						j += 1
						count += 1
					else:
						return False
				else:
					i += 1
					j += 1
			return True
		sort_words = sorted(words, key=len)
		res = [1 for i in range(len(sort_words))]
		for i in range(len(sort_words)):
			x = sort_words[i]
			for j in range(i, len(sort_words)):
				y = sort_words[j]
				if len(y) == len(x) + 1 and connected(y, x):
					res[j] = max(res[j], res[i] + 1)
				elif len(y) > len(x) + 1:
					break
		return max(res)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if len(words) == 0:
			return False
		words.sort(key=lambda x: len(x))

		def check(a, b):
			for i in range(len(b) - 1):
				if a[i] != b[i]:
					return b[i + 1:] == a[i:]
			return True
		ans = 1
		dp = [1] * len(words)
		for i in range(len(words)):
			for j in range(i + 1, len(words)):
				if len(words[j]) > 1 + len(words[i]):
					break
				if len(words[j]) == 1 + len(words[i]):
					if check(words[i], words[j]):
						dp[j] = max(dp[j], 1 + dp[i])
						ans = max(ans, dp[j])
		return ans


from collections import deque

def getKey(item):
	return len(item)

def isPred(word1, word2):
	word1 = list(word1)
	word2 = list(word2)
	q1 = deque(word1)
	q2 = deque(word2)
	while q1 and q2:
		if q1[0] == q2[0]:
			q1.popleft()
			q2.popleft()
		else:
			q2.popleft()
	if not q1 and len(q2) <= 1:
		return True
	return False

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=getKey)
		dp = [1] * len(words)
		for i in range(1, len(dp)):
			for j in reversed(list(range(0, i))):
				if len(words[j]) == len(words[i]):
					continue
				elif len(words[j]) + 1 == len(words[i]):
					if isPred(words[j], words[i]):
						dp[i] = max(dp[i], 1 + dp[j])
				else:
					break
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		n = len(words)
		words.sort(key=len)
		f = [1] * n

		def ispre(w1, w2):
			if len(w1) != len(w2) - 1:
				return False
			i = j = 0
			diff = False
			while i < len(w1) and j < len(w2):
				if w1[i] != w2[j]:
					if not diff:
						diff = True
						j += 1
						continue
					else:
						return False
				i += 1
				j += 1
			return True
		res = 1
		for i in range(1, n):
			for j in range(i):
				if ispre(words[j], words[i]):
					f[i] = max(f[i], f[j] + 1)
			res = max(res, f[i])
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if len(words) == 0:
			return 0

		def findDistance(shorterString, longerString):
			if len(longerString) - len(shorterString) != 1:
				return False
			(i, j) = (0, 0)
			edits = 0
			while j < len(shorterString):
				if longerString[i] != shorterString[j]:
					if edits == 0:
						i += 1
						edits += 1
						continue
					else:
						return False
				i += 1
				j += 1
			return True
		dp = [1] * len(words)
		words = sorted(words, key=lambda x: len(x))
		maxAnswer = 0
		for i in range(len(words)):
			temp = 1
			for j in range(i + 1):
				if findDistance(words[j], words[i]):
					temp = max(temp, dp[j] + 1)
			dp[i] = temp
			maxAnswer = max(maxAnswer, dp[i])
		return maxAnswer


def find(s1, s2):
	i = 0
	j = 0
	count = 0
	while i < len(s1) and j < len(s2):
		if s1[i] == s2[j]:
			i += 1
			j += 1
		else:
			j += 1
			count += 1
	if i == len(s1):
		return True
	if count == 1:
		return True
	return False

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		new_words = []
		for w in words:
			new_words.append((len(w), w))
		new_words.sort()
		dp = [1] * len(words)
		for i in range(len(words)):
			for j in range(i + 1, len(words)):
				(l1, w1) = new_words[i]
				(l2, w2) = new_words[j]
				if l2 - l1 > 1:
					break
				if l2 - l1 == 1:
					diff = find(w1, w2)
					if diff == 1:
						dp[j] = max(dp[j], dp[i] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		dp = collections.defaultdict(int)
		for word in words:
			dp[word] = max([dp[word[:i] + word[i + 1:]] for i in range(len(word))]) + 1
		return max(dp.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def if_pred(a, b):
			if len(a) + 1 != len(b):
				return False
			i = 0
			j = 0
			while i < len(a):
				if a[i] == b[j]:
					i += 1
				j += 1
				if j - i > 1:
					return False
			else:
				return True
		words.sort(key=lambda x: len(x))
		dp = [1 for _ in range(len(words))]
		for i in range(len(words)):
			for j in range(i - 1, -1, -1):
				if if_pred(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
		print(dp)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words_sort = [(len(word), word) for word in words]
		words_sort.sort()
		words = [word for (w_len, word) in words_sort]

		def isPredecessor(pre: str, succ: str) -> bool:
			if len(pre) != len(succ) - 1:
				return False
			pre = pre + '.'
			d = 0
			for i in range(len(succ)):
				if pre[i - d] != succ[i]:
					d += 1
					if d >= 2:
						return False
			return True
		chain = [1] * len(words)
		ans = 1
		for i in range(len(words)):
			for j in range(0, i):
				if isPredecessor(words[j], words[i]):
					chain[i] = max(chain[i], chain[j] + 1)
					ans = max(ans, chain[i])
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def determine(s1, s2):
			if len(s2) != len(s1) + 1:
				return False
			insert = False
			j = 0
			for i in range(len(s1)):
				while s2[j] != s1[i]:
					if insert:
						return False
					j = j + 1
					insert = True
				j = j + 1
			return True
		d = {}
		words = sorted(words, key=lambda x: len(x))
		d[words[-1]] = 1
		for i in reversed(list(range(len(words) - 1))):
			m = 0
			d[words[i]] = 1
			for j in range(i, len(words)):
				if determine(words[i], words[j]):
					if d[words[j]] > m:
						d[words[i]] = d[words[j]] + 1
						m = d[words[i]]
		out = 0
		for k in d:
			if d[k] > out:
				out = d[k]
		return out


from collections import Counter

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = [1] * len(words)
		words.sort(key=len)
		for i in range(1, len(words)):
			d1 = Counter(words[i])
			for j in range(i):
				if len(words[i]) - len(words[j]) == 1:
					d2 = Counter(words[j])
					check = 0
					for k in d1:
						if k not in d2:
							check += 1
						elif d2[k] != d1[k]:
							check += 1
						if check == 2:
							break
					if check == 1:
						dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def is_pred(short, long):
			if len(short) + 1 != len(long):
				return False
			short += ' '
			new = None
			for i in range(len(long)):
				if short[i] != long[i]:
					new = i
					break
			if short[:-1] == long[:new] + long[new + 1:]:
				return True
			return False
		words.sort(key=lambda x: len(x))
		dp = [1] * len(words)
		for i in range(1, len(words)):
			for j in range(i):
				if is_pred(words[j], words[i]):
					if dp[j] >= dp[i]:
						dp[i] = dp[j] + 1
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		self.res = 0

		def compare(w1, w2):
			if len(w1) > len(w2):
				(w1, w2) = (w2, w1)
			if len(w2) - len(w1) != 1:
				return False
			(i, j) = (0, 0)
			flag = False
			while i < len(w1) or j < len(w2):
				if i < len(w1) and w1[i] == w2[j]:
					i += 1
					j += 1
				elif not flag:
					flag = True
					j += 1
				else:
					return False
			return True

		@lru_cache(maxsize=None)
		def dfs(w):
			length = 0
			for word in words:
				if len(word) - len(w) == 1 and compare(w, word):
					length = max(dfs(word), length)
			ret = length + 1
			self.res = max(ret, self.res)
			return ret
		for w in words:
			dfs(w)
		return self.res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = {}
		words.sort(key=lambda x: len(x))
		for w in words:
			maxLen = 0
			for i in range(len(w)):
				predecessor = w[:i] + w[i + 1:]
				maxLen = max(maxLen, dp.get(predecessor, 0) + 1)
			dp[w] = maxLen
		return max(dp.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def check(w1, w2):
			if len(w1) != len(w2) - 1:
				return False
			cnt = 0
			idx1 = 0
			idx2 = 0
			while idx1 < len(w1) and idx2 < len(w2) and (cnt <= 1):
				if w1[idx1] == w2[idx2]:
					idx1 += 1
					idx2 += 1
				else:
					cnt += 1
					idx2 += 1
			if cnt == 0 and idx1 == len(w1) and (idx2 == len(w2) - 1):
				return True
			elif cnt == 1 and idx1 == len(w1) and (idx2 == len(w2)):
				return True
			else:
				return False
		words.sort(key=len)
		dp = [1 for _ in range(len(words))]
		for j in range(len(words)):
			for i in range(j):
				if check(words[i], words[j]):
					dp[j] = max(dp[j], dp[i] + 1)
		res = max(dp)
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def isPre(st1, st2):
			if len(st2) != len(st1) + 1:
				return False
			j = 0
			diff = 0
			for i in range(len(st2)):
				if diff > 1:
					return False
				elif j < len(st1) and st1[j] == st2[i]:
					j += 1
				else:
					diff += 1
			return diff <= 1
		words.sort(key=lambda x: len(x))
		n = len(words)
		dp = [1] * n
		for i in range(1, n):
			for j in range(i):
				if isPre(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def is_predessor(word1, word2):
			if abs(len(word1) - len(word2)) > 1:
				return False
			else:
				count = 0
				word1_cnt = 0
				word2_cnt = 0
				while word1 and word2:
					if word1[0] == word2[0]:
						word1 = word1[1:]
						word2 = word2[1:]
					else:
						count += 1
						word1 = word1[1:]
					if count > 1:
						return False
				return True
		words = sorted(words, key=lambda x: len(x))
		M = [0] * len(words)
		M[0] = 1
		overall_max = float('-inf')
		for i in range(1, len(M)):
			max_val = float('-inf')
			for j in range(i):
				if len(words[i]) != len(words[j]) and is_predessor(words[i], words[j]):
					max_val = max(max_val, 1 + M[j])
			M[i] = max(1, max_val)
			overall_max = max(overall_max, M[i])
		return overall_max


class Solution:

	def predecessor(self, larger, smaller):
		largerCount = Counter(larger)
		for c in smaller:
			if c in largerCount:
				largerCount[c] -= 1
				if largerCount[c] == 0:
					del largerCount[c]
		mc = largerCount.most_common()
		return len(mc) == 1 and mc[0][1] == 1

	def longestStrChain(self, words: List[str]) -> int:
		lengthToWords = defaultdict(list)
		for word in words:
			lengthToWords[len(word)].append(word)
		wordToCL = defaultdict(lambda : 1)
		res = 1
		for wordLength in range(16, 1, -1):
			if wordLength - 1 not in lengthToWords:
				continue
			for larger in lengthToWords[wordLength]:
				for smaller in lengthToWords[wordLength - 1]:
					if self.predecessor(larger, smaller):
						wordToCL[smaller] = max(wordToCL[smaller], wordToCL[larger] + 1)
						res = max(res, wordToCL[smaller])
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def is_predecessor(word_short, word_long) -> bool:
			if len(word_short) + 1 != len(word_long):
				return False
			i_s = 0
			can_skip = True
			for i_l in range(len(word_long)):
				if i_s > len(word_short) - 1:
					return True
				c_s = word_short[i_s]
				c_l = word_long[i_l]
				if c_s == c_l:
					i_s += 1
				elif can_skip:
					can_skip = False
					pass
				else:
					return False
			return True
		if not words:
			return 0
		words.sort(key=lambda x: len(x))
		dp = [1] * len(words)
		for r in range(1, len(words)):
			for l in range(r):
				if is_predecessor(words[l], words[r]):
					dp[r] = max(dp[r], dp[l] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def isPredecessor(w1, l1, w2, l2):
			if l2 == l1 + 1:
				for i in w1:
					if i not in w2:
						return False
				return True
			return False
		words.sort(key=lambda x: len(x))
		L = [len(i) for i in words]
		DP = [1 for i in range(len(L))]
		ans = 1
		for i in range(1, len(L)):
			for j in range(0, i):
				if isPredecessor(words[j], L[j], words[i], L[i]):
					DP[i] = max(DP[j] + 1, DP[i])
			ans = max(ans, DP[i])
		return ans


def isPredecessor(src, dst):
	nsrc = len(src)
	ndst = len(dst)
	if nsrc + 1 != ndst:
		return False
	i = 0
	while i < nsrc:
		if src[i] == dst[i]:
			i += 1
			continue
		else:
			return src[i:] == dst[i + 1:]
	return True

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		mem_len = [-1 for _ in range(len(words))]

		def search(i):
			if mem_len[i] != -1:
				return
			ans = 1
			for j in range(i + 1, len(words)):
				if isPredecessor(words[i], words[j]):
					search(j)
					ans = max(ans, mem_len[j] + 1)
			mem_len[i] = ans
		for i in range(len(words)):
			search(i)
		return max(mem_len)


from collections import defaultdict

class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def isPartOfChain(longer, shorter):
			if len(longer) - len(shorter) != 1:
				return False
			short_ptr = 0
			long_ptr = 0
			num_differences = 0
			while long_ptr <= len(longer):
				if num_differences > 1:
					return False
				if short_ptr > len(shorter) - 1:
					break
				if shorter[short_ptr] == longer[long_ptr]:
					short_ptr += 1
					long_ptr += 1
				else:
					long_ptr += 1
					num_differences += 1
			return True

		def longestHelp(words):
			if len(words) <= 1:
				return 1
			dp = [1 for _ in range(len(words))]
			max_length = 1
			for word in range(0, len(dp)):
				for j in range(word - 1, -1, -1):
					if isPartOfChain(words[word], words[j]):
						dp[word] = max(dp[word], 1 + dp[j])
						max_length = max(max_length, dp[word])
			return max_length
		words.sort(key=len)
		return longestHelp(words)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		n = len(words)
		lis = [1 for _ in range(n)]

		def cmp(w1, w2):
			for k in range(len(w1)):
				if w1[0:k] + w1[k + 1:] == w2:
					return True
			return False
		words = sorted(words, key=len)
		for i in range(1, n):
			for j in range(i):
				(l1, l2) = (len(words[j]), len(words[i]))
				if l1 == l2 - 1:
					if cmp(words[i], words[j]):
						if lis[i] < lis[j] + 1:
							lis[i] = lis[j] + 1
		return max(lis)


class Solution:

	def _is_pred(self, word1: str, word2: str) -> bool:
		if not len(word1) == len(word2) - 1:
			return False
		for c in word1:
			if c not in word2:
				return False
		return True

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		n = len(words)
		dp = [1 for i in range(n)]
		for i in range(n):
			for j in range(i):
				if self._is_pred(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words = sorted(words, key=lambda w: len(w))
		seenCache = {}
		max_len = 0
		for cur_word in words:
			cur_len = 0
			for i in range(len(cur_word)):
				check_word = cur_word[:i] + cur_word[i + 1:]
				cur_len = max(cur_len, seenCache.get(check_word, 0) + 1)
			seenCache[cur_word] = cur_len
			max_len = max(max_len, cur_len)
		return max_len


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		if not words:
			return 0
		n = len(words)
		dp = [1] * n
		for i in range(n):
			for j in range(i):
				if self.valid(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)

	def valid(self, str1, str2):
		if len(str1) + 1 != len(str2):
			return False
		cnt = 0
		n = len(str1)
		(l1, l2) = (0, 0)
		while l1 < n and l2 < n + 1:
			if cnt > 1:
				return False
			if str1[l1] != str2[l2]:
				l2 += 1
				cnt += 1
			else:
				l1 += 1
				l2 += 1
		return cnt <= 1


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		words.sort(key=lambda x: len(x))
		visited = set()
		res = 1
		for i in range(len(words)):
			if words[i] in visited:
				continue
			visited.add(words[i])
			res = max(res, self.dfs(words, words[i], i + 1, visited))
		return res

	def dfs(self, words, cur, start, visited):
		if start >= len(words):
			return 1
		ma = 1
		for i in range(start, len(words)):
			if len(words[i]) > len(cur) + 1:
				break
			if len(words[i]) == len(cur):
				continue
			if not self.isPredecessor(cur, words[i]):
				continue
			visited.add(words[i])
			ma = max(ma, 1 + self.dfs(words, words[i], i + 1, visited))
		return ma

	def isPredecessor(self, w1, w2):
		for i in range(len(w1)):
			if w1[:i] == w2[:i] and w1[i:] == w2[i + 1:]:
				return True
		if w1 == w2[:-1]:
			return True
		return False


class Solution:

	def can_move(self, a, b):
		b_letters = Counter(b)
		for char in a:
			b_letters[char] -= 1
			if b_letters[char] < 0:
				return False
			elif b_letters[char] == 0:
				b_letters.pop(char)
		return b_letters.popitem()[1] == 1

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda w: len(w))
		depths = {}

		def recur(index):
			if index not in depths:
				s = words[index]
				mx = 0
				for i in range(index + 1, len(words)):
					if len(words[i]) - len(s) == 1 and self.can_move(s, words[i]):
						mx = max(recur(i), mx)
				depths[index] = mx + 1
			return depths[index]
		for i in range(len(words)):
			recur(i)
		return max(depths.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		predecessors = dict()
		words = sorted(words, key=len)
		for i in range(len(words)):
			predecessors[words[i]] = []
			for j in range(i):
				if self.isPredecessor(words[i], words[j]):
					predecessors[words[i]].append((words[j], j))
		T = [0] * len(words)
		T[0] = 1
		for i in range(1, len(words)):
			if predecessors[words[i]]:
				T[i] = max([T[j[1]] for j in predecessors[words[i]]]) + 1
			else:
				T[i] = 1
		return max(T)

	def isPredecessor(self, word, candidate):
		if len(candidate) + 1 != len(word):
			return False
		(i, j) = (0, 0)
		wildcard = True
		while i < len(word) and j < len(candidate):
			if word[i] == candidate[j]:
				i += 1
				j += 1
			elif wildcard:
				i += 1
				wildcard = False
			else:
				return False
		return i + 1 == len(word) or i == len(word) if wildcard else i == len(word)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda word: len(word))
		lengths = [1] * len(words)
		for i in range(len(words)):
			for j in range(i):
				if self.checkifSuccessor(words[j], words[i]):
					lengths[i] = max(lengths[i], lengths[j] + 1)
		return max(lengths)

	def checkifSuccessor(self, word1, word2):
		if len(word1) + 1 != len(word2):
			return False
		else:
			indexOfword1 = 0
			differentReached = False
			for a in range(len(word2)):
				if indexOfword1 == len(word1):
					return True
				if word2[a] == word1[indexOfword1]:
					indexOfword1 += 1
				elif differentReached == True:
					return False
				else:
					differentReached = True
			return True


from collections import defaultdict

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = defaultdict(int)
		words.sort(key=lambda x: len(x))
		for w in words:
			maxLen = 0
			for i in range(len(w)):
				predecessor = w[:i] + w[i + 1:]
				maxLen = max(maxLen, dp[predecessor] + 1)
			dp[w] = maxLen
		return max(dp.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		N = len(words)

		def is_predecessor(word1: str, word2: str) -> bool:
			if len(word1) + 1 == len(word2):
				diffCount = 0
				(i, j) = (0, 0)
				while i < len(word1) and j < len(word2):
					if word1[i] == word2[j]:
						i += 1
						j += 1
					elif diffCount == 0:
						j += 1
						diffCount = 1
					else:
						return False
				return True
			return False

		def backtracking(start: int, count: int) -> int:
			if start in memo:
				return memo[start]
			sublongest = count
			for i in range(start + 1, N):
				if is_predecessor(words[start], words[i]):
					sublongest = max(sublongest, backtracking(i, count + 1))
			memo[start] = sublongest
			return sublongest
		words.sort(key=lambda x: (len(x), x))
		memo = dict()
		longest = 0
		for i in range(N):
			longest = max(longest, backtracking(i, 1))
		return longest


class Solution:

	def isPredecessor(self, predecessorCandidate, word):
		if len(predecessorCandidate) != len(word) - 1:
			return False
		pWhere = 0
		wWhere = 0
		hasSkipped = False
		while pWhere < len(predecessorCandidate) and wWhere < len(word):
			if predecessorCandidate[pWhere] != word[wWhere]:
				if hasSkipped:
					return False
				hasSkipped = True
				wWhere += 1
			else:
				wWhere += 1
				pWhere += 1
		return True

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		predecessorDict = collections.defaultdict(list)
		chainCountDict = collections.defaultdict(lambda : 1)
		currentMax = 1
		for i in range(0, len(words)):
			for j in range(i + 1, len(words)):
				if self.isPredecessor(words[i], words[j]):
					predecessorDict[words[j]].append(words[i])
					chainCountDict[words[j]] = max(chainCountDict[words[j]], 1 + chainCountDict[words[i]])
					currentMax = max(currentMax, chainCountDict[words[j]])
		return currentMax


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		n = len(words)
		dp = [1] * n
		words.sort(key=len)
		for i in range(1, n):
			for j in range(i):
				if self.is_predecessor(words[i], words[j]):
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)

	def is_predecessor(self, word1, word2):
		if len(word1) - len(word2) != 1:
			return False
		i1 = 0
		i2 = 0
		diff = 0
		while i1 < len(word1) and i2 < len(word2):
			if word1[i1] == word2[i2]:
				i1 += 1
				i2 += 1
			else:
				i1 += 1
				diff += 1
				if diff > 1:
					return False
		return True


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		n = len(words)
		words.sort(key=len)
		f = [1] * n

		def ispre(w1, w2):
			if len(w1) != len(w2) - 1:
				return False
			it = iter(w2)
			return all((c in it for c in w1))
		res = 1
		for i in range(1, n):
			for j in range(i):
				if ispre(words[j], words[i]):
					f[i] = max(f[i], f[j] + 1)
			res = max(res, f[i])
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def helper(a, b):
			(i, j) = (0, 0)
			diff = 0
			while i < len(a) and j < len(b):
				if a[i] == b[j]:
					i += 1
					j += 1
				else:
					i += 1
					diff += 1
			if i < len(a):
				diff += len(a) - i
			if j < len(b):
				diff += len(b) - j
			if diff > 1:
				return False
			else:
				return True
		dp = [1] * len(words)
		words = sorted(words, key=len)
		for i in range(len(words)):
			for j in range(i):
				if len(words[i]) - len(words[j]) == 1 and helper(words[i], words[j]):
					dp[i] = max(dp[i], dp[j] + 1)
		print(dp)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		max_len = [1] * len(words)
		res = 1
		for i in range(len(words) - 1):
			for j in range(i, len(words)):
				if self.isPredecessor(words[i], words[j]):
					max_len[j] = max(max_len[i] + 1, max_len[j])
					res = max(res, max_len[j])
		return res

	def isPredecessor(self, s1, s2):
		if len(s2) - len(s1) != 1:
			return False
		flag = 0
		(i, j) = (0, 0)
		while i < len(s1) and j < len(s2):
			if s1[i] == s2[j]:
				i += 1
				j += 1
			elif flag == 0:
				flag = 1
				j += 1
			else:
				return False
		return True


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def chain(w1, w2):
			(m, n) = (len(w1), len(w2))
			if abs(m - n) != 1:
				return False
			(i, j, one) = (0, 0, 1)
			while i < m and j < n:
				if w1[i] == w2[j]:
					(i, j) = (i + 1, j + 1)
				elif one:
					(one, i) = (0, i + 1)
				else:
					return False
			return True
		if not words:
			return 0
		words.sort(key=lambda x: len(x))
		n = len(words)
		dp = [1] * n
		ans = 1
		for i in range(n):
			for j in range(i):
				if chain(words[i], words[j]):
					dp[i] = max(dp[i], dp[j] + 1)
			ans = max(ans, dp[i])
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words = sorted(words, key=lambda x: len(x))
		DP = [0 for i in words]
		max_len = 0
		for i in range(len(words)):
			length = []
			for j in range(1, i + 1):
				if len(words[i - j]) < len(words[i]) - 1:
					break
				elif len(words[i - j]) == len(words[i]) - 1:
					if self.check(words[i - j], words[i]) == True:
						length.append(DP[i - j])
			if length:
				DP[i] = max(length) + 1
			else:
				DP[i] = 1
		return max(DP)

	def check(self, word1, word2):
		val = 0
		for i in range(len(word1)):
			if word1[i] != word2[i]:
				if val == 0:
					word2 = word2[:i] + word2[i + 1:]
					return word1 == word2
				if val == 1:
					return False
				continue
		return True


class Solution:

	def longer_by_one(self, word1, word2):
		if len(word2) - len(word1) != 1:
			return False
		j = 0
		count = 0
		for i in range(len(word2)):
			if i < len(word2) and j < len(word1) and (word2[i] != word1[j]):
				count += 1
				if count > 1:
					return False
				continue
			j += 1
		if i == len(word2) - 1 and j == len(word1) and (count == 1):
			return True
		elif i == len(word2) - 1 and j >= len(word1) and (count == 0):
			return True
		else:
			return False

	def longestStrChain(self, words: List[str]) -> int:
		dp = [1] * len(words)
		words = sorted(words, key=lambda x: len(x))
		for i in range(1, len(words)):
			for j in range(0, i):
				if self.longer_by_one(words[j], words[i]) == True:
					dp[i] = max(dp[i], dp[j] + 1)
		for i in range(len(dp)):
			print((words[i], dp[i]))
		return max(dp)


from collections import defaultdict

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		words = sorted(words, key=lambda x: len(x))
		dp = [1 for _ in range(len(words))]
		res = 1
		for i in range(1, len(words)):
			for j in range(i):
				if len(words[j]) + 1 == len(words[i]) and self.isPred(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
			res = max(res, dp[i])
		return res

	def isPred(self, word1, word2):
		if len(word1) + 1 != len(word2):
			return False
		p1 = 0
		p2 = 0
		degree = 0
		while p1 < len(word1) and p2 < len(word2):
			if word1[p1] == word2[p2]:
				p1 += 1
				p2 += 1
				continue
			else:
				degree += 1
				p2 += 1
		return degree < 2


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = {}
		result = 1
		for word in sorted(words, key=lambda x: -len(x)):
			dp[word] = 1
			for i in range(len(word) + 1):
				for c in 'abcdefghijklmnopqrstuvwxyz':
					next_word = word[:i] + c + word[i:]
					if next_word in dp:
						dp[word] = max(dp[word], dp[next_word] + 1)
						result = max(result, dp[word])
		return result


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		longestchain = defaultdict(int)
		words.sort(key=len, reverse=True)
		for word in words:
			for i in range(len(word)):
				pred = word[:i] + word[i + 1:]
				longestchain[pred] = max(longestchain[pred], 1 + longestchain[word])
		return max(longestchain.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words = sorted(words, key=lambda word: len(word))
		n = len(words)
		if n == 1:
			return 1
		ans = 1
		dp = [1] * n

		def match(i, j):
			idx_i = 0
			idx_j = 0
			skipped = False
			while idx_j < len(words[j]):
				if words[i][idx_i] != words[j][idx_j]:
					if skipped:
						return False
					skipped = True
					idx_i += 1
				else:
					idx_i += 1
					idx_j += 1
			return True
		for i in range(1, n):
			for j in range(i - 1, -1, -1):
				if len(words[i]) - len(words[j]) > 1:
					break
				elif len(words[i]) - len(words[j]) == 1:
					if match(i, j):
						dp[i] = max(dp[i], dp[j] + 1)
						ans = max(ans, dp[i])
				else:
					pass
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words = sorted(words, key=lambda w: len(w))
		dp = [None] * len(words)
		dp[0] = 1
		for i in range(1, len(words)):
			maxi = 1
			for j in list(range(0, i))[::-1]:
				if self.check(words[j], words[i]) and dp[j] + 1 > maxi:
					maxi = dp[j] + 1
			dp[i] = maxi
		return max(dp)

	def check(self, chain, word):
		if len(chain) + 1 != len(word):
			return False
		i = 0
		j = 0
		Flag = False
		while i < len(chain) and j < len(word):
			if chain[i] == word[j]:
				i += 1
				j += 1
			elif chain[i] != word[j] and (not Flag):
				j += 1
				Flag = True
			else:
				return False
		return True


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0

		def isPred(p, q, words):
			w1 = words[p]
			w2 = words[q]
			n2 = len(w2)
			res = False
			for i in range(n2):
				if w1 == w2[0:i] + w2[i + 1:]:
					res = True
			return res
		n = len(words)
		dpR = [1] * n
		wR = sorted(words, key=len)
		for i in range(n):
			cur = 1
			for j in range(i):
				n1 = len(wR[j])
				n2 = len(wR[i])
				if n2 - n1 != 1:
					continue
				if isPred(j, i, wR):
					cur = max(cur, dpR[j] + 1)
			dpR[i] = cur
		return max(dpR)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		print(words)
		solutions = []
		numWords = len(words)
		for i in range(numWords):
			self.getSequences(words[i + 1:], len(words[i]) + 1, [words[i]], words[i], solutions)
		maxSize = 0
		for s in solutions:
			maxSize = max(maxSize, len(s))
		return maxSize

	def getSequences(self, words, targetLength, currSequence, lastWord, solutions):
		numWords = len(words)
		for i in range(numWords):
			if len(words[i]) == targetLength:
				if self.isPredecessor(lastWord, words[i]):
					newCurrSequence = currSequence[:]
					newCurrSequence.append(words[i])
					self.getSequences(words[i + 1:], targetLength + 1, newCurrSequence, words[i], solutions)
			elif len(words[i]) > targetLength:
				break
		if len(solutions) > 0:
			if len(solutions[0]) < len(currSequence):
				solutions[0] = currSequence
		else:
			solutions.append(currSequence)
		return

	def isPredecessor(self, word1, word2):
		numLetters1 = len(word1)
		numLetters2 = len(word2)
		if numLetters2 - numLetters1 != 1:
			return False
		p1 = 0
		p2 = 0
		count = 0
		while p1 < numLetters1:
			if word1[p1] == word2[p2]:
				p1 += 1
				p2 += 1
			elif count == 1:
				return False
			else:
				count += 1
				p2 += 1
		return True


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def check(w1, w2):
			idx = 0
			for i in range(len(w2)):
				if w2[i] == w1[idx]:
					idx += 1
				if idx == len(w1):
					return True
			return False
		n = len(words)
		words.sort(key=lambda w: len(w))
		G = [[] for _ in range(n)]
		for i in range(n):
			for j in range(i + 1, n):
				if len(words[j]) - len(words[i]) > 1:
					break
				if len(words[j]) - len(words[i]) == 1 and check(words[i], words[j]):
					G[i].append(j)

		def rec(v):
			if memo[v] != -1:
				return memo[v]
			res = 1
			for nv in G[v]:
				res = max(res, rec(nv) + 1)
			memo[v] = res
			return res
		memo = [-1] * n
		ans = 0
		for i in range(n):
			ans = max(ans, rec(i))
		return ans


class Solution:

	def check(self, word1, word2) -> bool:
		if len(word1) + 1 != len(word2):
			return False
		for i in range(len(word1) + 1):
			if i < len(word1) and word1[i] == word2[i]:
				continue
			else:
				word2 = word2[:i] + word2[i + 1:]
				return word1 == word2

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		output = [0 for i in range(len(words))]
		for j in range(-1, -len(words) - 1, -1):
			temp_len = 1
			k = j + 1
			while k <= -1:
				if temp_len < output[k] + 1:
					if self.check(words[j], words[k]):
						temp_len = output[k] + 1
				k += 1
			output[j] = temp_len
		return max(output)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		li = {word: 1 for word in words}
		words.sort(key=len)
		ans = 1
		for word in words:
			for i in range(len(word)):
				new = word[:i] + word[i + 1:]
				if new in words:
					if li[word] < li[new] + 1:
						li[word] = li[new] + 1
						if li[word] > ans:
							ans = li[word]
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		longestchain = defaultdict(int)
		for word in sorted(words, key=len):
			for i in range(len(word)):
				longestchain[word] = max(longestchain[word[:i] + word[i + 1:]] + 1, longestchain[word])
		return max(longestchain.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = [0] * len(words)
		words.sort(key=lambda x: len(x))

		def predecessor(a, b):
			if len(a) == len(b):
				return False
			diff = 0
			i = 0
			j = 0
			while i < len(a) and j < len(b):
				if a[i] != b[j]:
					diff += 1
					if diff >= 2:
						return False
					i += 1
				else:
					i += 1
					j += 1
			return True
		for (i, word) in enumerate(words):
			dp[i] = 1
			for j in range(i - 1, -1, -1):
				if len(words[i]) - len(words[j]) >= 2:
					break
				if predecessor(words[i], words[j]):
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def is_seq(word1, word2):
			if len(word2) != len(word1) + 1:
				return False
			L = len(word2)
			for idx in range(L):
				if word1 == word2[:idx] + word2[idx + 1:]:
					return True
			return False
		L = len(words)
		dp = [1 for w in words]
		words = sorted(words, key=lambda x: len(x))
		for idx in range(L):
			word2 = words[idx]
			for j in range(idx):
				word1 = words[j]
				if is_seq(word1, word2):
					dp[idx] = max(dp[idx], dp[j] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		dp = [1 for _ in words]
		for start in range(len(words)):
			for end in range(start - 1, -1, -1):
				if len(words[end]) < len(words[start]) - 1:
					break
				if predecessor(words[start], words[end]):
					dp[start] = max(dp[start], 1 + dp[end])
		return max(dp)

def predecessor(word, candidate):
	if len(word) != len(candidate) + 1:
		return False
	j = 0
	for (i, c) in enumerate(word):
		if i > j + 1 or j == len(candidate):
			break
		if c == candidate[j]:
			j += 1
	return j == len(candidate)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def pred(a, b):
			if len(a) == len(b) or len(a) - len(b) > 1:
				return False
			diff = 0
			i = 0
			j = 0
			while i < len(a):
				if a[i] == b[j]:
					i += 1
					j += 1
				else:
					diff += 1
					if diff > 1:
						return False
					j += 1
			return True
		if not words:
			return 0
		dp = [0 for w in words]
		ret = 0
		words.sort(key=len)
		for i in range(len(words)):
			dp[i] = 1
			for j in range(i):
				if len(words[i]) - len(words[j]) <= 1 and pred(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
			ret = max(ret, dp[i])
		return ret


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		from collections import defaultdict, deque
		hash_map = defaultdict(list)
		visited = {}
		max_len = 0
		q = deque()
		for char in words:
			if len(char) > 1:
				neighbors = [char[:i] + char[i + 1:] for i in range(len(char))]
				for n in neighbors:
					hash_map[n].append(char)
			hash_map[char].append(char)
		words.sort(key=len)
		for word in words:
			q.appendleft((word, 1))
		while q:
			(char, count) = q.pop()
			if char not in visited and char in hash_map:
				max_len = max(max_len, count)
				for n in hash_map[char]:
					q.append((n, count + 1))
			visited[char] = 1
		return max_len


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def isPredecessor(a, b):
			if len(a) != len(b) - 1 or len(b) == 1:
				return False
			for i in range(len(b)):
				tmp = b[:i] + b[i + 1:]
				if a == tmp:
					return True
			return False
		words.sort(key=len)
		dp = [1] * len(words)
		for i in range(len(dp)):
			for j in range(i - 1, -1, -1):
				if isPredecessor(words[j], words[i]):
					dp[i] = max(dp[j] + 1, dp[i])
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = [0 for i in range(len(words))]
		ans = 0
		words = sorted(words, key=lambda x: len(x))
		for i in range(len(words)):
			for j in range(i):
				if self.prev(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
					ans = max(ans, dp[i])
		return ans + 1

	def prev(self, word_1, word_2):
		(len_1, len_2) = (len(word_1), len(word_2))
		if len_1 + 1 != len_2:
			return False
		i = j = 0
		while i < len_1 and j < len_2:
			if word_1[i] == word_2[j]:
				i += 1
			j += 1
		if i == len_1:
			return True
		else:
			return False


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		print(words)
		sequence = collections.defaultdict(list)
		dp = [1] * len(words)
		for i in range(len(words)):
			for j in range(0, i):
				predecessor = self.checkPredecessor(words[j], words[i])
				if predecessor:
					sequence[words[i]].append(words[j])
					dp[i] = max(dp[j] + 1, dp[i])
		print(sequence)
		print(list(zip(words, dp)))
		return max(dp)

	def checkPredecessor(self, word1, word2):
		if len(word2) - len(word1) > 1:
			return False
		elif len(word1) == len(word2):
			return False
		i = j = 0
		diff = False
		while i < len(word1):
			if word1[i] == word2[j]:
				i += 1
				j += 1
			elif not diff:
				diff = True
				j += 1
			else:
				return False
		if i == len(word1) and j < len(word2) and diff:
			return False
		return True


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words = sorted(words, key=len)

		def onediff(word1, word2):
			if len(word1) + 1 != len(word2):
				return False
			for i in range(len(word2)):
				if word2[:i] + word2[i + 1:] == word1:
					return True
			return False
		dp = [1] * len(words)
		for i in range(len(words)):
			for j in range(i):
				if onediff(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


from collections import Counter

class Solution:

	def is_one_away(self, str_1, str_2):
		c1 = Counter(str_1)
		c2 = Counter(str_2)
		diff = 0
		for (k, v) in c2.items():
			diff += v - c1.get(k, 0)
			if diff > 1:
				return False
		for k in c1:
			if k not in c2:
				return False
		return True

	def longestStrChain(self, words: List[str]) -> int:
		sorted_words = sorted([''.join(sorted(w)) for w in words], key=lambda x: len(x))
		dp = [1] * len(words)
		for i in range(len(sorted_words) - 1, -1, -1):
			for j in range(i - 1, -1, -1):
				if len(sorted_words[i]) - len(sorted_words[j]) == 0:
					continue
				if len(sorted_words[i]) - len(sorted_words[j]) > 1:
					break
				if self.is_one_away(sorted_words[j], sorted_words[i]):
					dp[j] = max(1 + dp[i], dp[j])
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def is_predecessor(x, y):
			if len(x) != len(y) - 1:
				return False
			i = 0
			j = 0
			while i < len(x) and j < len(y):
				if x[i] == y[j]:
					i += 1
					j += 1
				else:
					j += 1
			if i == len(x):
				return True
			return False
		words = sorted(words, key=lambda x: len(x))
		n = len(words)
		dp = [1] * n
		for i in range(1, n):
			for j in range(i):
				if is_predecessor(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda w: len(w))
		word_chains = {w: 1 for w in words}
		for word in words:
			for i in range(len(word)):
				sub_word = word[:i] + word[i + 1:]
				if sub_word in words:
					word_chains[word] = max(word_chains[sub_word] + 1, word_chains[word])
		return max(word_chains.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = {}
		res = 1
		for word in sorted(words, key=len):
			for i in range(len(word)):
				if word[:i] + word[i + 1:] in words:
					dp[word] = dp.get(word[:i] + word[i + 1:], 1) + 1
					res = max(res, dp[word])
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		words.sort(key=lambda x: len(x))
		n = len(words)
		dp = [1 for i in range(n)]
		for i in range(1, n):
			for j in range(i):
				if self.is_predecessor(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)

	def is_predecessor(self, word1, word2):
		if len(word1) + 1 != len(word2):
			return False
		(i, j) = (0, 0)
		while i < len(word1) and j < len(word2):
			if word1[i] == word2[j]:
				i += 1
				j += 1
			else:
				j += 1
		return i == len(word1)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		n = len(words)
		words = [(len(word), word) for word in words]
		words.sort()
		words = [word[1] for word in words]
		dp = [1 for i in range(n)]
		for i in range(n):
			for j in reversed(list(range(i))):
				if len(words[j]) < len(words[i]) - 1:
					break
				if len(words[j]) == len(words[i]):
					continue
				if self.check(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)

	def check(self, s1, s2):
		(i, j) = (0, 0)
		count = 0
		while i < len(s1) and j < len(s2):
			if s1[i] == s2[j]:
				i += 1
				j += 1
			else:
				j += 1
				count += 1
		return i == len(s1)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def pre(word2, word):
			if len(word2) + 1 == len(word):
				for i in range(len(word)):
					if word[:i] + word[i + 1:] == word2:
						return True
			return False
		words = sorted(words, key=lambda x: -len(x))
		best = 0
		n = len(words)
		length = [0] * n
		for i in range(n):
			for j in range(i + 1, n):
				if pre(words[j], words[i]):
					length[j] = max(length[j], length[i] + 1)
					best = max(best, length[j])
		return best + 1


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		l = [1 for i in range(len(words))]
		words.sort(key=lambda x: len(x))
		res = [[i] for i in words]
		for i in range(1, len(words)):
			for j in range(i):
				if len(words[j]) + 1 == len(words[i]):
					x = {}
					for a in words[j]:
						if a in x:
							x[a] += 1
						else:
							x[a] = 1
					ctr = 0
					for a in words[i]:
						if a not in x:
							ctr += 1
						elif x[a] == 0:
							ctr += 1
						else:
							x[a] -= 1
					if ctr == 1 and l[i] < l[j] + 1:
						res[i] = [i for i in res[j]]
						res[i].append([words[i]])
						l[i] = l[j] + 1
		return max(l)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words = sorted(words, key=lambda w: len(w))
		total = len(words)
		count = [1 for _ in range(total)]
		for i in range(1, total):
			for j in range(i):
				if self.predecessor(words[j], words[i]) and count[i] < count[j] + 1:
					count[i] = count[j] + 1
		return max(count)

	def predecessor(self, word1, word2):
		if len(word2) != len(word1) + 1:
			return False
		for i in range(len(word2)):
			subword = word2[:i] + word2[i + 1:]
			if subword == word1:
				return True
		return False


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		N = len(words)
		self.longest = [None] * N
		max_len = 1
		for i in range(N):
			max_len = max(max_len, self.__findLongestAfter(words, i))
		return max_len

	def __isPredecessor(self, w1, w2):
		if len(w2) != len(w1) + 1:
			return False
		for i in range(len(w2)):
			if w2[:i] + w2[i + 1:] == w1:
				return True
		return False

	def __findLongestAfter(self, words: List[str], i: int) -> int:
		if self.longest[i] is not None:
			return self.longest[i]
		max_len = 1
		for j in range(i + 1, len(words)):
			if self.__isPredecessor(words[i], words[j]):
				max_len = max(max_len, self.__findLongestAfter(words, j) + 1)
		self.longest[i] = max_len
		return max_len


class Solution:

	def predecessor(self, w1, w2):
		i = 0
		diffs = 0
		while i < len(w1):
			if w1[i] != w2[i]:
				diffs = 1
				break
			i += 1
		if diffs == 0:
			return True
		return w1 == w2[:i] + w2[i + 1:]

	def longestStrChain(self, words):
		words = sorted(words, key=lambda x: len(x))
		words_by_len = {}
		for w in words:
			if len(w) in words_by_len:
				words_by_len[len(w)].append(w)
			else:
				words_by_len[len(w)] = [w]
		max_lens = {}
		for w in words:
			max_lens[w] = 1
		for l in words_by_len:
			if l - 1 in words_by_len:
				for w1 in words_by_len[l]:
					for w2 in words_by_len[l - 1]:
						if self.predecessor(w2, w1):
							max_lens[w1] = max(max_lens[w1], 1 + max_lens[w2])
		max_len = 0
		for w in max_lens:
			max_len = max(max_len, max_lens[w])
		return max_len


class Solution:

	def longestStrChain(self, wordlist: List[str]) -> int:
		wl = set(wordlist)

		def dfs(w):
			if len(w) == 1:
				return 1
			if w in memo:
				return memo[w]
			l = len(w)
			depth = 0
			for i in range(l):
				next = w[0:i] + w[i + 1:l]
				if next in wordlist:
					depth = max(depth, dfs(next))
			memo[w] = depth + 1
			return depth + 1
		memo = {}
		longest = 1
		for word in wordlist:
			longest = max(longest, dfs(word))
		return longest


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def helper(word_pre, word_cur):
			if len(word_pre) - len(word_cur) != -1:
				return False
			(count, pre, cur) = (0, 0, 0)
			while pre <= len(word_pre) and cur < len(word_cur):
				if pre < len(word_pre) and word_cur[cur] == word_pre[pre]:
					pre += 1
				else:
					count += 1
				cur += 1
			return True if count == 1 else False
		dp = [1] * len(words)
		words = sorted(words, key=len)
		for i in range(len(words)):
			for j in range(i):
				if helper(words[j], words[i]) and dp[j] > dp[i] - 1:
					dp[i] = dp[j] + 1
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		d = {w: 1 for w in words}
		words.sort(key=lambda x: len(x))

		def check(w1, w2):
			if len(w1) <= len(w2):
				return False
			if len(w1) - len(w2) == 1:
				i = 0
				j = 0
				count = 0
				while i < len(w1) and j < len(w2):
					if w1[i] == w2[j]:
						i += 1
						j += 1
					else:
						i += 1
						count += 1
				if count > 1:
					return False
				else:
					return True
			return False
		dp = [0 for _ in range(len(words))]
		dp[0] = 1
		res = 1
		for i in range(1, len(words)):
			curr_max = 0
			for j in range(i):
				if check(words[i], words[j]):
					curr_max = max(curr_max, dp[j])
			dp[i] = curr_max + 1
			res = max(res, dp[i])
		return res


class Solution:

	def isPredecessor(self, word1, word2):
		if len(word1) + 1 == len(word2):
			i = 0
			j = 0
			count = 0
			while i < len(word1) and j < len(word2):
				if word1[i] != word2[j]:
					count += 1
				else:
					i += 1
				j += 1
			if count > 1:
				return False
			elif count == 0:
				if len(word2) == j + 1:
					return True
			else:
				return True
		else:
			return False

	def memoization(self, i, words, memo):
		if i >= len(words):
			return 0
		if memo[i] is not None:
			return memo[i]
		length = 0
		for j in range(i + 1, len(words)):
			if self.isPredecessor(words[i], words[j]):
				length = max(length, self.memoization(j, words, memo))
		memo[i] = 1 + length
		return memo[i]

	def longestStrChain(self, words: List[str]) -> int:
		words = sorted(words, key=len)
		memo = [None] * len(words)
		length = 0
		for i in range(len(words)):
			length = max(length, self.memoization(i, words, memo))
		return length


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words = sorted(words, key=lambda x: len(x))
		dp = [1] * len(words)
		res = 1
		for i in range(len(words)):
			for j in range(0, i):
				if len(words[i]) > len(words[j]) and self.isPrecessor(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
					res = max(res, dp[i])
		return res

	def isPrecessor(self, word1, word2):
		ind1 = 0
		ind2 = 0
		flag = 0
		while ind1 < len(word1) and ind2 < len(word2):
			if word1[ind1] == word2[ind2]:
				ind1 += 1
				ind2 += 1
			else:
				if flag == 1:
					return False
				ind2 += 1
				flag = 1
		return ind1 == len(word1) and ind2 == len(word2) or (ind1 == len(word1) and flag == 0 and (ind2 + 1 == len(word2)))


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		sort = [[] for _ in range(max(map(len, words)))]
		for el in words:
			sort[len(el) - 1].append(el)
		d = collections.defaultdict(int)
		for row in sort:
			for w in row:
				for i in range(len(w)):
					l = w[:i] + w[i + 1:]
					t = d[l] + 1
					d[w] = max(d[w], t)
		return max(d.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		N = len(words)
		self.longest = [None] * N
		max_len = 1
		for i in range(N):
			max_len = max(max_len, self.__findLongestAfter(words, i))
		return max_len

	def __isPredecessor(self, w1, w2):
		if len(w2) != len(w1) + 1:
			return False
		i = j = 0
		while i < len(w1) and j < len(w2):
			if w1[i] == w2[j]:
				i += 1
			j += 1
		return i == len(w1)

	def __findLongestAfter(self, words: List[str], i: int) -> int:
		if self.longest[i] is not None:
			return self.longest[i]
		self.longest[i] = 1
		len_i = len(words[i])
		for j in range(i + 1, len(words)):
			if len(words[j]) > len_i + 1:
				break
			if self.__isPredecessor(words[i], words[j]):
				self.longest[i] = max(self.longest[i], self.__findLongestAfter(words, j) + 1)
		return self.longest[i]


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		dp = [1] * len(words)
		for i in range(len(words)):
			curr = words[i]
			for j in range(i):
				prev = words[j]
				if self.isPredecessor(curr, prev):
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)

	def isPredecessor(self, curr, prev):
		if len(curr) - len(prev) != 1:
			return False
		i = j = 0
		diff = False
		while i < len(curr) and j < len(prev):
			if curr[i] == prev[j]:
				i += 1
				j += 1
			else:
				if diff:
					return False
				diff = True
				i += 1
		return True


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		print(words)
		n_s = len(words[0])
		dic = collections.defaultdict(lambda : 0)
		longest_chain = 1

		def search(word):
			if len(word) == n_s:
				dic[word] = 1
				return 1
			N = 1
			for i in range(0, len(word)):
				sub = word[0:i] + word[i + 1:]
				if sub in words:
					n = search(sub)
					N = max(N, n + 1)
			dic[word] = N
			nonlocal longest_chain
			longest_chain = max(longest_chain, N)
			return N
		for i in range(len(words) - 1, -1, -1):
			if dic[words[i]] in dic:
				continue
			word = words[i]
			re = search(word)
			longest_chain = max(longest_chain, re)
		return longest_chain


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		wset = set(words)
		memo = {}

		def dp(word):
			if word in memo:
				return memo[word]
			ans = 1
			for i in range(len(word) + 1):
				for j in range(26):
					newword = word[:i] + chr(ord('a') + j) + word[i:]
					if newword in wset:
						ans = max(ans, 1 + dp(newword))
			memo[word] = ans
			return ans
		ret = 0
		for word in words:
			if not word in memo:
				ret = max(ret, dp(word))
		return ret


class Solution:

	def isSubString(self, s1, s2):
		diff = 0
		l = len(s1)
		ll = len(s2)
		if ll - l != 1:
			return False
		i = 0
		j = 0
		diff = 0
		while i < l and diff < 2:
			if s1[i] == s2[j]:
				i += 1
				j += 1
			else:
				j += 1
				diff += 1
		if diff > 1:
			return False
		return True

	def longestStrChain(self, words: List[str]) -> int:
		n = len(words)
		words = sorted(words, key=len)
		dp = [1] * n
		for i in range(n):
			j = i - 1
			while j >= 0 and len(words[i]) - len(words[j]) <= 1:
				if self.isSubString(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
				j -= 1
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		di = defaultdict(list)
		for w in words:
			di[len(w)].append(w)
		(L, U) = (min(di.keys()), max(di.keys()))
		dp = [1] * len(di[L])
		ans = 1

		def ispred(w1, w2):
			skip = False
			for i in range(len(w1)):
				while w1[i] != w2[i + skip]:
					if skip:
						return False
					skip = True
			return True
		for l in range(L + 1, U + 1):
			old = dp
			dp = [1] * len(di[l])
			for (j, w2) in enumerate(di[l]):
				tmp = [old[i] for (i, w1) in enumerate(di[l - 1]) if ispred(w1, w2)]
				if tmp:
					dp[j] = max(tmp) + 1
			ans = max(ans, max(dp))
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		n = len(words)

		def extraChar(s1, s2):
			(l1, l2) = (sorted(s1), sorted(s2))
			diff = 0
			(i, j) = (0, 0)
			if len(s1) == len(s2) + 1:
				while i < len(s1) and j < len(s2):
					if l1[i] != l2[j]:
						i += 1
						diff += 1
					else:
						i += 1
						j += 1
				if i == len(s1) and j == len(s2):
					return diff == 1
				elif i == len(s1) - 1:
					return True
			return False
		mem = {}
		words.sort(key=lambda x: len(x))

		def dp(i):
			if i >= n:
				return 0
			if i in mem:
				return mem[i]
			mem[i] = 1
			for j in range(i + 1, n):
				if len(words[j]) == len(words[i]) + 1 and extraChar(words[j], words[i]):
					mem[i] = max(mem[i], dp(j) + 1)
				elif len(words[j]) > len(words[i]) + 1:
					break
			return mem[i]
		return max([dp(i) for i in range(n)])


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		mark = {}
		queue = []
		for (index, word) in enumerate(words):
			mark[word] = collections.Counter(word)
			queue.append([[word], index, len(word)])
		ans = 0
		while queue:
			(s, index, l) = queue.pop(0)
			flag = True
			for i in range(index + 1, len(words)):
				if len(words[i]) > l + 1:
					break
				if len(words[i]) == l + 1:
					add = True
					sum1 = 0
					sum2 = 0
					for key in list(mark[s[-1]].keys()):
						if key not in mark[words[i]]:
							add = False
							break
						sum1 += mark[s[-1]][key]
						sum2 += mark[words[i]][key]
					if add and (sum1 == sum2 or sum2 - sum1 == 1):
						queue.append([s + [words[i]], i, l + 1])
						flag = False
			if flag:
				ans = max(ans, len(s))
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		hashmap = collections.defaultdict(list)
		for (index, word) in enumerate(words):
			hashmap[len(word)].append(index)
		n = len(words)
		graph = [[False for _ in range(n)] for _ in range(n)]

		def predecessor(a, b):
			mistake = 0
			for i in range(len(a)):
				if a[i] != b[i + mistake]:
					mistake += 1
					if mistake > 1 or a[i] != b[i + mistake]:
						return False
			return True
		for (index, word) in enumerate(words):
			for candidate in hashmap[len(word) + 1]:
				if predecessor(word, words[candidate]):
					graph[index][candidate] = True
		dp = [-1 for _ in range(n)]

		def dfs(i):
			if dp[i] != -1:
				return dp[i]
			answer = 0
			for j in range(n):
				if graph[i][j]:
					answer = max(answer, dfs(j))
			dp[i] = answer + 1
			return answer + 1
		answer = 0
		for i in range(n):
			answer = max(answer, dfs(i))
		return answer


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def is_edit(a, b):
			if abs(len(a) - len(b)) > 1:
				return False
			if len(a) == len(b):
				return False
			for i in range(min(len(a), len(b))):
				if a[i] != b[i]:
					return a == b[:i] + b[i + 1:] or b == a[:i] + a[i + 1:]
			return True
		words.sort(key=lambda x: len(x))
		n = len(words)
		memo = [1 for _ in range(n)]
		ans = 1
		for i in range(n - 1, -1, -1):
			max_ = 0
			for j in range(i + 1, n):
				if is_edit(words[i], words[j]):
					max_ = max(max_, memo[j])
			memo[i] = 1 + max_
			ans = max(memo[i], ans)
		return ans


from collections import Counter

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = [1]
		res = 0
		words = sorted(words, key=lambda x: len(x))
		for i in range(1, len(words)):
			j = i - 1
			val = 1
			while j >= 0:
				if len(words[j]) != len(words[i]) - 1:
					j -= 1
					continue
				(counter_j, counter_i) = (Counter(words[j]), Counter(words[i]))
				used = False
				for (key, value_j) in counter_j.items():
					value_i = counter_i.get(key)
					if not value_i or value_i > value_j + 1 or value_i < value_j:
						break
					if value_i == value_j + 1 and used:
						break
					if value_i == value_j + 1 and (not used):
						used = True
				else:
					val = max(val, dp[j] + 1)
				j -= 1
			dp.append(val)
			res = max(val, res)
		print(dp)
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def isPred(word1, word2):
			for i in range(len(word2)):
				if word2[0:i] + word2[i + 1:] == word1:
					return True
			return False
		graph = {}
		for i in range(len(words) - 1):
			for j in range(i + 1, len(words)):
				(w1, w2) = (words[i], words[j])
				if len(w2) - len(w1) == 1 and isPred(w1, w2):
					if w1 in graph:
						graph[w1].append(w2)
					else:
						graph[w1] = [w2]
				elif len(w2) - len(w1) == -1 and isPred(w2, w1):
					if w2 in graph:
						graph[w2].append(w1)
					else:
						graph[w2] = [w1]
		self.res = 0

		def dfs(word, lev):
			self.res = max(self.res, lev)
			if word not in graph:
				return
			for i in graph[word]:
				dfs(i, lev + 1)
		for i_word in words:
			dfs(i_word, 1)
		return self.res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		st = set(words)

		def ls(word):
			res = 1
			for j in range(len(word)):
				substr = word[:j] + word[j + 1:]
				if substr not in st:
					continue
				res = 1 + ls(substr)
			return res
		res = 1
		for word in words:
			res = max(res, ls(word))
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		N = len(words)
		dp = [1] * N
		words.sort(key=len)
		print(words)
		if N == 1:
			return 1

		def check(word1, word2):
			if len(word2) - len(word1) != 1:
				return False
			n = len(word1)
			for i in range(n):
				if word2[:i] + word2[i + 1:] == word1:
					return True
				if word2[:-1] == word1:
					return True
			return False
		for i in range(N):
			for j in range(i):
				if check(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		word_dict = {}
		words = [(len(w), w) for w in words]
		words = sorted(words)
		for (_, w) in words:
			word_dict[w] = 1
		state_t = set()
		max_chain = 1
		for (_, word) in words:
			chain_len = word_dict[word]
			max_chain = max(max_chain, chain_len)
			for i in range(len(word) + 1):
				for c in range(97, 123):
					new_word = word[:i] + chr(c) + word[i:]
					if word_dict.get(new_word, False) and new_word not in state_t:
						state_t.add(new_word)
						word_dict[new_word] = chain_len + 1
		return max_chain


from collections import defaultdict

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		length = defaultdict(list)
		for s in words:
			length[len(s)].append(s)
		record = sorted(list(length.items()), reverse=True)
		result = defaultdict(int)
		max_length = 1
		for item in record:
			for word in item[1]:
				if result[word] == 0:
					result[word] += 1
				for i in range(len(word)):
					new_string = word[0:i] + word[i + 1:]
					if new_string in words:
						result[new_string] = max(result[new_string], result[word] + 1)
						max_length = max(max_length, result[new_string])
		return max_length


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dic = defaultdict(list)
		words.sort(key=len, reverse=True)
		for w in words:
			for i in range(len(w)):
				if w[:i] + w[i + 1:] in words:
					dic[w].append(w[:i] + w[i + 1:])

		def bt(x):
			return [[x]] if x not in dic else [[x] + rest for y in dic[x] for rest in bt(y)]
		ct = 1
		for word in words:
			ct = max(ct, len(max(bt(word), key=len)))
		return ct


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		dp = [1 for _ in words]
		largest = 1
		words.sort(key=lambda s: len(s))
		print(words)

		def predecessor(big_word, small_word):
			b = 0
			s = 0
			mismatch = False
			if len(small_word) + 1 != len(big_word):
				return False
			while b < len(big_word) and s < len(small_word):
				if big_word[b] != small_word[s] and (not mismatch):
					mismatch = True
					b += 1
					continue
				elif big_word[b] == small_word[s]:
					s += 1
					b += 1
					continue
				else:
					return False
			return True
		left = 0
		right = 0
		while right < len(words):
			for k in range(left, right):
				if len(words[k]) == words[right]:
					left = right
					break
				if predecessor(words[right], words[k]):
					dp[right] = max(dp[right], dp[k] + 1)
					largest = max(dp[right], largest)
			right += 1
		return largest


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		words.sort(key=lambda x: len(x))
		counter = [collections.Counter(word) for word in words]
		dp = [1] * len(words)
		maxlen = 0
		for i in range(len(dp)):
			for j in range(i):
				if len(words[i]) - len(words[j]) == 1 and len(counter[i] - counter[j]) == 1:
					dp[i] = max(dp[i], 1 + dp[j])
			maxlen = max(maxlen, dp[i])
		return maxlen


class Solution:

	def __init__(self):
		self.cache = collections.defaultdict(int)

	def longestEndWith(self, word, words):
		if word in self.cache:
			return self.cache[word]
		if len(word) == 1:
			self.cache[word] = 1
			return 1
		else:
			for i in range(len(word)):
				s = word[:i] + word[i + 1:]
				if s in words:
					self.cache[word] = max(self.cache[word], self.longestEndWith(s, words))
			self.cache[word] += 1
			return self.cache[word]

	def longestStrChain(self, words: List[str]) -> int:
		ans = 0
		for word in words:
			ans = max(ans, self.longestEndWith(word, words))
		return ans


class Solution:

	def __init__(self):
		self.cache = collections.defaultdict(int)

	def longestEndWith(self, word, words):
		if word in self.cache:
			return self.cache[word]
		if len(word) == 1:
			self.cache[word] = 1
			return 1
		else:
			for i in range(len(word)):
				s = word[:i] + word[i + 1:]
				if s in words:
					self.cache[word] = max(self.cache[word], self.longestEndWith(s, words))
			self.cache[word] += 1
			return self.cache[word]

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		ans = 0
		for word in words[::-1]:
			if word not in self.cache:
				ans = max(ans, self.longestEndWith(word, words))
		return ans


from collections import defaultdict

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		ends_at = defaultdict(int)
		words = sorted(words, key=lambda x: len(x))
		ans = 0
		for w in words:
			ends_at[w] = 1
			for (i, ch) in enumerate(w):
				prev = w[:i] + w[i + 1:]
				if prev in words:
					ends_at[w] = max(ends_at[w], ends_at[prev] + 1)
			ans = max(ans, ends_at[w])
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = {}

		def chainEndingAt(word):
			if word not in words:
				return 0
			if word not in dp:
				chain_len = 1
				for i in range(len(word)):
					pred = word[:i] + word[i + 1:]
					chain_len = max(chain_len, chainEndingAt(pred) + 1)
				dp[word] = chain_len
			return dp[word]
		ans = 0
		for word in words:
			ans = max(ans, chainEndingAt(word))
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words = sorted(words, key=len)
		n = len(words)

		def match(l, r):
			a = words[l]
			b = words[r]
			if len(a) + 1 != len(b):
				return False
			(i, j) = (0, 0)
			while i < len(a) and j < len(b):
				if a[i] == b[j]:
					i += 1
				j += 1
			return i == len(a)
		dp = [0 for _ in range(n)]
		for i in range(n - 2, -1, -1):
			for j in range(i + 1, n):
				if len(words[j]) > len(words[i]) + 1:
					break
				if match(i, j):
					dp[i] = max(dp[i], 1 + dp[j])
		return 1 + max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dictByLen = collections.defaultdict(list)
		wordCounter = {}
		for (i, w) in enumerate(words):
			dictByLen[len(w)].append(w)
			wordCounter[w] = collections.Counter(w)

		def isOneDiff(s1, s2):
			diff = 0
			j = 0
			for c in s2:
				if c != s1[j]:
					if diff == 1:
						return False
					diff += 1
				else:
					j += 1
					if j == len(s1):
						return True
			return True
		sortedLens = sorted(dictByLen.keys())
		longestLen = 1
		prevLen = -1
		for l in sortedLens:
			if prevLen == -1 or l != prevLen + 1:
				prevArr = [(s, 1) for s in dictByLen[l]]
			else:
				newArr = []
				for s2 in dictByLen[l]:
					diff = 1
					for (s1, lsf) in prevArr:
						if isOneDiff(s1, s2):
							diff = max(diff, lsf + 1)
					newArr.append((s2, diff))
					longestLen = max(diff, longestLen)
				prevArr = newArr
			prevLen = l
		return longestLen


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda w: len(w))
		graph = {}
		indegree = {}
		for w in words:
			graph[w] = []
			indegree[w] = 0

		def is_pre(wd_sml, wd_lrg):
			for idx in range(len(wd_lrg)):
				if wd_lrg[:idx] + wd_lrg[idx + 1:] == wd_sml:
					return True
			return False
		for idx in range(1, len(words)):
			for idx2 in range(idx):
				if len(words[idx]) != len(words[idx2]) + 1:
					continue
				if is_pre(words[idx2], words[idx]):
					graph[words[idx2]].append(words[idx])
					indegree[words[idx]] += 1
		memo = {}
		from collections import deque

		def dfs(wd):
			if wd in memo:
				return memo[wd]
			res = 1
			for nei in graph[wd]:
				res = max(res, 1 + dfs(nei))
			memo[wd] = res
			return memo[wd]
		st_arr = [w for (w, indeg) in list(indegree.items()) if not indeg]
		max_len = 0
		for elt in st_arr:
			res_len = dfs(elt)
			max_len = max(res_len, max_len)
		return max_len


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def edit_dist(w1, w2):
			n = len(w1)
			m = len(w2)
			if n + 1 != m:
				return False
			mismatch = 0
			i = 0
			j = 0
			while i < n and j < m:
				if w1[i] != w2[j]:
					mismatch += 1
					j += 1
				else:
					i += 1
					j += 1
			return mismatch <= 1

		def recurse(word, length):
			nonlocal max_l
			max_l = max(max_l, length)
			n = len(word) + 1
			if n in dic:
				for next_word in dic[n]:
					if edit_dist(word, next_word):
						recurse(next_word, length + 1)
		dic = collections.defaultdict(list)
		for word in words:
			dic[len(word)].append(word)
		max_l = 0
		for word in words:
			recurse(word, 1)
		return max_l


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		word_graph = {}
		for word in words:
			for second_word in words:
				if len(second_word) == len(word) + 1:
					is_predecessor = True
					second_word_counter = Counter(second_word)
					first_word_counter = Counter(word)
					for (key, value) in list(first_word_counter.items()):
						if second_word_counter[key] < value:
							is_predecessor = False
							break
					if is_predecessor:
						if word in word_graph:
							word_graph[word].append(second_word)
						else:
							word_graph[word] = [second_word]
		max_level = 1
		for (key, value) in list(word_graph.items()):
			queue = deque()
			queue.append((key, 1))
			visted = set()
			while queue:
				(curr, level) = queue.popleft()
				if level > max_level:
					max_level = level
				if curr in word_graph:
					for next_word in word_graph[curr]:
						queue.append((next_word, level + 1))
		return max_level


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		explored = set()
		stack = [(word, 1) for word in sorted(words, key=len, reverse=True)]
		words = set(words)
		best = 1
		while stack:
			(word, chain_length) = stack.pop()
			best = max(best, chain_length)
			for candidate_word in [word[:i] + c + word[i:] for c in 'abcdefghijklmnopqrstuvwxyz' for i in range(len(word) + 1)]:
				if candidate_word in words and candidate_word not in explored:
					stack.append((candidate_word, chain_length + 1))
					explored.add(candidate_word)
		return best


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def dfs(str):
			dep = 1
			for longer_str in words:
				if len(longer_str) == len(str) + 1:
					for i in range(len(str) + 1):
						new_str = longer_str[:i] + longer_str[i + 1:]
						if new_str == str:
							dep = max(dep, dfs(longer_str) + 1)
							seen.append(longer_str)
			return dep
		seen = []
		depth = []
		words = sorted(words, key=len)
		for str in words:
			if str not in seen:
				depth.append(dfs(str))
		return max(depth)


from collections import Counter

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))

		def helper(s1, s2):
			if len(s1) != len(s2) - 1:
				return False
			s1 = Counter(s1)
			s2 = Counter(s2)
			diff = 0
			for j in s2:
				if j not in s1:
					diff += 1
				elif s2[j] != s1[j]:
					diff += 1
				if diff >= 2:
					return False
			return diff == 1
		dps = [1 for _ in words]
		for j in range(len(words)):
			_max = 1
			for i in range(j):
				if helper(words[i], words[j]):
					_max = max(_max, dps[i] + 1)
			dps[j] = _max
		return max(dps)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))
		wordLevels = {}
		for word in words:
			if len(word) in wordLevels:
				wordLevels[len(word)].append(word)
			else:
				wordLevels[len(word)] = [word]
		result = 0
		words.reverse()
		for word in words:
			result = max(result, self.getChain(word, wordLevels, 1))
		return result

	def getChain(self, word, wordLevels, length):
		level = len(word)
		for i in range(len(word)):
			if level - 1 in wordLevels:
				if word[:i] + word[i + 1:] in wordLevels[level - 1]:
					return self.getChain(word[:i] + word[i + 1:], wordLevels, length + 1)
		return length


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		x = lambda a: len(a)
		words.sort(key=x)
		print(words)
		chain_len = [None] * len(words)
		chain_len[0] = 1
		for i in range(1, len(words)):
			temp = words[i]
			chain_len[i] = 1
			for j in range(len(temp)):
				temp2 = temp[:j] + temp[j + 1:]
				if temp2 not in words:
					continue
				for k in range(i - 1, -1, -1):
					if len(words[k]) < len(words[i]) - 1:
						break
					elif len(words[k]) == len(words[i]) - 1:
						if words[k] == temp2:
							chain_len[i] = max(chain_len[i], chain_len[k] + 1)
							break
		return max(chain_len)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words = sorted(words, key=lambda x: len(x))
		pred = [1] * len(words)

		def diff1(w1, w2):
			for i in range(len(w2)):
				if w2[:i] + w2[i + 1:] == w1:
					return True
			return False

		def diff2(w1, w2):
			i = 0
			while i < len(w1) and w1[i] == w2[i]:
				i += 1
			j = len(w1) - 1
			while j >= i and w1[j] == w2[j + 1]:
				j -= 1
			if j == i - 1:
				return True
			return False
		for i in range(len(words)):
			j = i - 1
			while j >= 0 and abs(len(words[j]) - len(words[i])) < 2:
				if len(words[j]) == len(words[i]) - 1 and diff2(words[j], words[i]):
					pred[i] = max(pred[i], pred[j] + 1)
				j -= 1
		return max(pred)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		print(words)

		def stringmatch(s1, s2):
			onemismatchallowed = True
			if len(s1) > len(s2):
				(s2, s1) = (s1, s2)
			if len(s1) + 1 != len(s2):
				return False
			(i, j) = (0, 0)
			while i < len(s1):
				if s1[i] != s2[j]:
					if onemismatchallowed == True:
						onemismatchallowed = False
					else:
						return False
					j += 1
				else:
					i += 1
					j += 1
			return True
		dp = [1 for _ in range(len(words))]
		ans = 1
		for i in range(1, len(words)):
			j = i - 1
			while j >= 0 and len(words[j]) + 1 >= len(words[i]):
				val = stringmatch(words[j], words[i])
				if val:
					print(words[j], words[i])
					print(dp[i])
					dp[i] = max(dp[j] + 1, dp[i])
					ans = max(dp[i], ans)
				j -= 1
		print(dp)
		return ans


class Solution:

	def __init__(self):
		self.results = []
		self.explored = dict()

	def traverse(self, string, listt, buffer):
		flag = True
		for i in range(len(string)):
			if string[:i] + string[i + 1:] in listt:
				flag = False
				self.traverse(string[:i] + string[i + 1:], listt, buffer + [string[:i] + string[i + 1:]])
		if flag:
			self.results.append(buffer)
			for item in buffer:
				self.explored[item] = True
		return

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len, reverse=True)
		for word in words:
			if word not in self.explored:
				self.traverse(word, words, [word])
		return len(max(self.results, key=len))


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def is_predecessor(str1, str2):
			if len(str1) + 1 != len(str2):
				return False
			else:
				for i in range(len(str2)):
					if str1 == str2[:i] + str2[i + 1:]:
						return True
				return False
		l = len(words)
		words.sort(key=len)
		mat = [[0 for j in range(l)] for i in range(l)]
		mat_max = 0
		for i in range(l):
			for j in range(i, l):
				if is_predecessor(words[i], words[j]):
					mat[i][j] = mat[i][i] + 1
					mat[j][j] = max(mat[j][j], mat[i][j])
					mat_max = max(mat_max, mat[i][j])
		return mat_max + 1


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def pred(origin, dest):
			if len(dest) - len(origin) != 1:
				return False
			misWord = False
			oIndex = 0
			for index in range(len(dest)):
				if oIndex == len(origin):
					if misWord == False:
						return True
					return False
				if dest[index] != origin[oIndex]:
					if misWord:
						return False
					misWord = True
					continue
				oIndex += 1
			return True
		table = {}

		def helper(node):
			longest = 0
			if node in table:
				return table[node]
			for word in words:
				if pred(node, word):
					longest = max(helper(word), longest)
			table[node] = longest + 1
			return longest + 1
		maxPos = 0
		for word in words:
			maxPos = max(maxPos, helper(word))
		return maxPos


class Solution:

	def _check_word(self, wordlong, word2) -> bool:
		if len(wordlong) - len(word2) > 1 or len(wordlong) - len(word2) == 0:
			return False
		for i in range(0, len(wordlong)):
			newstr = wordlong[:i] + wordlong[i + 1:]
			if newstr == word2:
				return True
		return False

	def longestStrChain(self, words: List[str]) -> int:
		if len(words) == 1:
			return words[0]
		words = sorted(words, key=len, reverse=True)
		m = [1] * len(words)
		for i in range(1, len(words)):
			for j in range(0, i):
				if self._check_word(words[j], words[i]) and m[j] + 1 > m[i]:
					m[i] = m[j] + 1
		return max(m)


from collections import defaultdict, deque

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		lookup_neighbors = defaultdict(list)
		for word in words:
			word_length: int = len(word)
			lookup_neighbors[word_length].append(word)

		def is_next_word_valid(current_word: str, next_word: str) -> bool:
			current_word_length = len(current_word)
			for index in range(current_word_length):
				if next_word == current_word[0:index] + current_word[index + 1:]:
					return True
			return False
		maximum_chain = 0
		for word in reversed(words):
			frontier = deque([(word, 1)])
			while frontier:
				next_frontier = deque()
				while frontier:
					(current_word, distance) = frontier.popleft()
					current_word_length = len(current_word)
					maximum_chain = max(maximum_chain, distance)
					for neighbor in lookup_neighbors[current_word_length - 1]:
						if is_next_word_valid(current_word, neighbor):
							next_frontier.append((neighbor, distance + 1))
				frontier = next_frontier
		return maximum_chain


from collections import Counter, defaultdict

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		length_to_words = defaultdict(list)
		for word in words:
			length_to_words[len(word)].append(word)
		lengths = sorted(length_to_words.keys(), reverse=True)
		successors = defaultdict(list)
		for length in lengths:
			for word in length_to_words[length]:
				for predecessor_candidate in length_to_words[length - 1]:
					if predecessor(predecessor_candidate, word):
						successors[predecessor_candidate].append(word)
		max_lengths = {}
		for length in lengths:
			for word in length_to_words[length]:
				if word in successors:
					max_lengths[word] = 1 + max([max_lengths[s] for s in successors[word]])
				else:
					max_lengths[word] = 1
		return max(max_lengths.values())

def predecessor(word1, word2):
	word1_counts = Counter(word1)
	word2_counts = Counter(word2)
	letters = set(word1 + word2)
	diff = [abs(word1_counts[l] - word2_counts[l]) for l in letters]
	nonzero_diff = [d for d in diff if d > 0]
	if len(nonzero_diff) != 1:
		return False
	if nonzero_diff[0] != 1:
		return False
	return True


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		wordsListLength = len(words)
		if wordsListLength <= 1:
			return wordsListLength

		def isPredecessor(word1, word2):
			for i in range(len(word2)):
				if word2[:i] + word2[i + 1:] == word1:
					return True
			return False
		words.sort(key=lambda x: len(x))
		result = 1
		dp = [1 for _ in range(wordsListLength)]
		for i in range(wordsListLength):
			for j in range(i + 1, wordsListLength):
				if len(words[i]) + 1 == len(words[j]) and isPredecessor(words[i], words[j]):
					dp[j] = dp[i] + 1
					result = max(result, dp[j])
		return result


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		wordCounter = [collections.Counter(x) for x in words]
		dp = [1 for _ in range(len(words))]
		for i in range(len(words) - 2, -1, -1):
			for j in range(i + 1, len(words)):
				if len(words[i]) == len(words[j]):
					continue
				if len(words[j]) - len(words[i]) > 1:
					break
				if len(wordCounter[j] - wordCounter[i]) == 1:
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		dic = collections.Counter()
		res = 0
		for word in words:
			for i in range(len(word)):
				pre = word[:i] + word[i + 1:]
				dic[word] = max(dic[word], dic[pre] + 1)
			res = max(res, dic[word])
		return res


class Solution:

	def one_off(self, a, b):
		if abs(len(a) - len(b)) != 1:
			return False
		one_off = False
		i = 0
		j = 0
		while i < len(a) and j < len(b):
			if a[i] != b[j]:
				if one_off:
					return False
				one_off = True
				if len(a) > len(b):
					j -= 1
				else:
					i -= 1
			i += 1
			j += 1
		return True

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		words.sort(key=lambda word: -len(word))
		dp = {}
		best = 1
		for (i, word) in enumerate(words):
			for other in words[i + 1:]:
				if len(word) - 1 > len(other):
					break
				if self.one_off(word, other):
					dp[other] = max(dp.get(other, 0), dp.get(word, 1) + 1)
					best = max(best, dp[other])
		return best


from collections import Counter

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda x: len(x))

		def check_predecessor(s1, s2):
			if len(s1) != len(s2) - 1:
				return False
			for i in range(len(s2)):
				if s1 == s2[:i] + s2[i + 1:]:
					return True
			return False
		dp = [1] * len(words)
		res = 1
		for i in range(len(words)):
			for j in range(i):
				if check_predecessor(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
					res = max(res, dp[i])
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		graph = defaultdict(list)
		in_degrees = defaultdict(int)
		for w1 in words:
			for w2 in words:
				if self.isPredecessor(w1, w2):
					graph[w2].append(w1)
					in_degrees[w1] += 1
		max_len = 1
		queue = deque([(w, 1) for w in graph if in_degrees[w] == 0])
		while queue:
			(word, path_len) = queue.popleft()
			for child in graph[word]:
				in_degrees[child] -= 1
				if in_degrees[child] == 0:
					queue.append((child, path_len + 1))
			max_len = path_len
		return max_len

	def isPredecessor(self, w1, w2):
		if len(w1) != len(w2) + 1:
			return False
		i1 = 0
		i2 = 0
		added = False
		while i1 < len(w1) and i2 < len(w2):
			if w1[i1] != w2[i2] and added:
				return False
			elif w1[i1] != w2[i2]:
				i1 += 1
				added = True
			else:
				i1 += 1
				i2 += 1
		return True


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		sorted(words, key=len, reverse=True)
		depth = [1] * len(words)

		def dfs(word):
			depth = 1
			for i in range(len(word)):
				new_word = word[:i] + word[i + 1:]
				if new_word in words:
					depth = max(dfs(new_word) + 1, depth)
			seen.append(word)
			return depth
		count = []
		seen = []
		for word in words:
			if word not in seen:
				count.append(dfs(word))
		return max(count)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		preToPost = collections.defaultdict(set)
		for word1 in words:
			for word2 in words:
				if self.isPredecessor(word1, word2):
					preToPost[word1].add(word2)
		ans = 0
		memo = {}
		for word in words:
			ans = max(ans, self.dfs(word, preToPost, memo))
		return ans

	def dfs(self, word, preToPost, memo):
		if word in memo:
			return memo[word]
		ans = 1
		for post in preToPost[word]:
			ans = max(ans, 1 + self.dfs(post, preToPost, memo))
		memo[word] = ans
		return memo[word]

	def isPredecessor(self, word1, word2):
		if not len(word1) + 1 == len(word2):
			return False
		missed = False
		i = 0
		j = 0
		while i < len(word1) and j < len(word2) and (word1[i] == word2[j]):
			i += 1
			j += 1
		j += 1
		while i < len(word1) and j < len(word2) and (word1[i] == word2[j]):
			i += 1
			j += 1
		return i == len(word1) and j == len(word2)


class Solution:

	def longestStrChain(self, words) -> int:
		len_words = len(words)
		dp = [1] * len_words
		res = 0
		words.sort(key=len)
		for i in range(len_words):
			max_value = 0
			for j in range(i):
				if not self.checkChild(words[j], words[i]):
					continue
				max_value = max(max_value, dp[j])
			dp[i] = max_value + 1
			res = max(res, dp[i])
		return res

	def checkChild(self, word1, word2):
		if len(word1) != len(word2) - 1:
			return False
		from collections import Counter
		counter1 = Counter(word1)
		count = 0
		for ch in word2:
			if ch in counter1:
				counter1[ch] -= 1
				if counter1[ch] == 0:
					counter1.pop(ch)
			else:
				count += 1
			if count > 1:
				return False
		return True


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def isPredecessor(word1, word2):
			if len(word1) + 1 != len(word2):
				return False
			(i, j, count) = (0, 0, 0)
			while i < len(word1):
				if word1[i] != word2[j]:
					count += 1
					j += 1
					if count > 1:
						return False
					continue
				i += 1
				j += 1
			return True
		numPredecessor = [0] * len(words)
		graph = defaultdict(lambda : [])
		for i in range(len(words)):
			for j in range(i + 1, len(words)):
				if isPredecessor(words[i], words[j]):
					graph[i].append(j)
					numPredecessor[j] += 1
				elif isPredecessor(words[j], words[i]):
					graph[j].append(i)
					numPredecessor[i] += 1

		def dfs(node, path):
			nonlocal out
			path.append(node)
			out = max(out, len(path))
			for nei in graph[node]:
				dfs(nei, path)
			path.pop()
		out = 0
		for node in [i for i in range(len(words)) if not numPredecessor[i]]:
			dfs(node, [])
		return out


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		children = collections.defaultdict(set)
		for i in range(len(words)):
			for j in range(len(words)):
				if len(words[i]) == len(words[j]) + 1:
					for k in range(len(words[i])):
						if words[i][:k] + words[i][k + 1:] == words[j]:
							children[words[j]].add(words[i])
		print(children)

		def dfs(w, count):
			visited.add(w)
			if not children[w]:
				self.res = max(self.res, count)
			else:
				for v in children[w]:
					dfs(v, count + 1)
		visited = set()
		self.res = 0
		for u in words:
			if u not in visited:
				dfs(u, 1)
		return self.res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		word_map = collections.defaultdict(int)
		word_list = collections.defaultdict(list)
		ans = 1
		for word in words:
			length = len(word)
			word_list[length].append(word)
			word_map[word] = 1
		for word_len in range(1, 17):
			if word_len not in word_list:
				continue
			for word in word_list[word_len]:
				pre_len = word_len - 1
				if pre_len not in word_list:
					break
				for pre_word in word_list[pre_len]:
					if self.is_predecessor(pre_word, word):
						word_map[word] = max(word_map[word], word_map[pre_word] + 1)
						ans = max(ans, word_map[word])
		return ans

	def is_predecessor(self, w1, w2):
		(idx1, idx2) = (0, 0)
		once = False
		while idx1 < len(w1) and idx2 < len(w2):
			if w1[idx1] == w2[idx2]:
				idx1 += 1
				idx2 += 1
			elif once:
				return False
			else:
				once = True
				idx2 += 1
		return True


from collections import defaultdict

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		n = len(words)
		words.sort(key=len)
		memo = {}

		def check_pred(word1, word2):
			if len(word2) - len(word1) != 1:
				return False
			for i in range(len(word2)):
				pred_str = word2[0:i] + word2[i + 1:]
				if word1 == pred_str:
					return True
			return False

		def recur(start):
			if start in memo:
				return memo[start]
			f_max = 1
			for i in range(start + 1, n):
				c_max = 1
				if check_pred(words[start], words[i]):
					c_max = 1 + recur(i)
				f_max = max(f_max, c_max)
			memo[start] = f_max
			return f_max
		ans = 0
		for i in range(n):
			ans = max(ans, recur(i))
		return ans


from collections import defaultdict

class Solution:

	def is_neighbor(self, s1, s2):
		ss = s1
		bs = s2
		neighbor = False
		for i in range(len(ss) + 1):
			padded_str = ss[:i] + '*' + ss[i:]
			for (p1, p2) in zip(padded_str, bs):
				neighbor = p1 == '*' or p1 == p2
				if not neighbor:
					break
			if neighbor:
				return neighbor
	path_len = 1

	def build_chains(self, chain_graph, start_key, visited=set(), curr_path=2):
		visited.add(start_key)
		for string in chain_graph[start_key] - visited:
			if string in chain_graph:
				self.build_chains(chain_graph, string, visited, curr_path + 1)
			else:
				print(('term:', string, curr_path + 1))
				self.path_len = max(self.path_len, curr_path + 1)

	def longestStrChain(self, words: List[str]) -> int:
		str_chain_graph = defaultdict(set)
		for w1 in words:
			for w2 in words:
				if len(w2) - len(w1) == 1:
					neighbor = self.is_neighbor(w1, w2)
					if neighbor:
						str_chain_graph[w1].add(w2)
		for key in str_chain_graph:
			self.build_chains(str_chain_graph, key, set(), 1)
		return self.path_len


class Solution:

	def string1(self, s1, s2):
		if abs(len(s1) - len(s2)) > 1 or abs(len(s1) - len(s2)) == 0:
			return False
		i = 0
		j = 0
		k = 0
		while i < len(s1) and j < len(s2):
			if k > 1:
				return False
			if s1[i] != s2[j]:
				k += 1
				if len(s1) > len(s2):
					i += 1
				else:
					j += 1
			else:
				i += 1
				j += 1
		return True if k <= 1 else False

	def longestStrChain(self, words: List[str]) -> int:
		words = sorted(words, key=len, reverse=True)
		d = {}
		l = len(words[0])
		m = 1
		for i in range(len(words)):
			w = words[i]
			m = max([m] + list(d.values()))
			d = {key: val for (key, val) in list(d.items()) if len(key) <= len(w) + 1}
			d[w] = 1
			for (key, val) in list(d.items()):
				if self.string1(key, w):
					d[w] = max(d[w], d[key] + 1)
			l = len(w)
		return max([m] + list(d.values()))


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def isPred(w1, w2):
			if len(w1) + 1 != len(w2):
				return False
			flag = 0
			for i in range(len(w1)):
				if w1[i] != w2[i + flag] and flag == 0:
					flag = 1
					if w1[i] != w2[i + flag]:
						return False
				elif w1[i] != w2[i + flag] and flag != 0:
					return False
			return True

		def dfs(i):
			if i in memo:
				return memo[i]
			max_level = 0
			for next_i in graph[i]:
				level = dfs(next_i)
				if level > max_level:
					max_level = level
			memo[i] = max_level + 1
			return memo[i]
		n = len(words)
		if n <= 1:
			return n
		graph = collections.defaultdict(list)
		for i in range(n):
			for j in range(n):
				if isPred(words[i], words[j]):
					graph[i].append(j)
		memo = {}
		ans = 0
		for i in range(n):
			level = dfs(i)
			if level > ans:
				ans = level
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		cache = {}
		words_dict = {word: None for word in words}

		def chain(word):
			if word in cache:
				return cache[word]
			if word in words:
				cache[word] = 1 + max(map(chain, [word[:idx] + word[idx + 1:] for idx in range(len(word))]))
				return cache[word]
			return 0
		return max(map(chain, words))


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def custom_equal(word1, word2):
			if len(word2) == len(word1):
				return 0
			for i in range(len(word2)):
				if word2[0:i] + word2[i + 1:] == word1:
					return 1
			return 0
		words.sort(key=lambda x: len(x))
		max_len = 1
		dp = [1 for _ in words]
		for i in range(1, len(words)):
			for j in range(i - 1, -1, -1):
				if len(words[j]) + 1 < len(words[i]):
					break
				if custom_equal(words[j], words[i]):
					dp[i] = max(dp[i], dp[j] + 1)
				max_len = max(max_len, dp[i])
		return max_len


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		(ans, dicti, memo) = (0, collections.defaultdict(list), collections.defaultdict(int))
		for word in words:
			dicti[len(word)].append(word)
		chars = [chr(ch) for ch in range(ord('a'), ord('z') + 1)]

		def find(count, word):
			if word in memo:
				return count + memo[word]
			if len(word) + 1 not in dicti:
				memo[word] = 0
				return count
			maxi = 0
			for i in range(len(word) + 1):
				for ch in chars:
					new_word = word[:i] + ch + word[i:]
					if new_word in dicti[len(word) + 1]:
						maxi = max(maxi, find(1, new_word))
			memo[word] = maxi
			return count + memo[word]
		for word in sorted(words, key=lambda x: len(x)):
			el = find(1, word)
			ans = max(ans, el)
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		n = len(words)
		lis = defaultdict(int)
		words = sorted(words, key=len)
		print(words)
		ans = 0
		for i in range(n):
			w = words[i]
			for j in range(len(words[i])):
				s = w[0:j] + w[j + 1:]
				lis[w] = max(lis[w], lis[s] + 1)
			ans = max(ans, lis[w])
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		self.memo = {}
		self.ans = 1
		self.words = set(words)
		for word in self.words:
			self.dfs(word)
		return self.ans

	def dfs(self, word):
		if len(word) == 1:
			self.memo[word] = 1
			return 1
		self.memo[word] = 1
		for i in range(len(word)):
			nxt = word[:i] + word[i + 1:]
			if nxt in self.words:
				self.memo[word] = max(self.memo[word], 1 + self.dfs(nxt))
				self.ans = max(self.ans, self.memo[word])
		return self.memo[word]


from collections import defaultdict

class Solution:

	def is_one_apart(self, word1, word2):
		assert len(word1) >= len(word2)
		length_diff = len(word1) - len(word2)
		if length_diff != 1:
			return False
		i = 0
		j = 0
		while i < len(word1) and j < len(word2):
			if word1[i] == word2[j]:
				i += 1
				j += 1
			elif i - j >= 1:
				return False
			else:
				i += 1
		return True

	def longestStrChain(self, words: List[str]) -> int:
		length_words = defaultdict(list)
		chain_lengths = {}
		max_chain = 1
		for word in words:
			length_words[len(word)].append(word)
			chain_lengths[word] = 1
		for length in sorted(list(length_words.keys()), reverse=True):
			if length - 1 not in length_words:
				continue
			for word1 in length_words[length]:
				for word2 in length_words[length - 1]:
					if chain_lengths[word1] + 1 <= chain_lengths[word2]:
						continue
					if self.is_one_apart(word1, word2):
						chain_lengths[word2] = chain_lengths[word1] + 1
						max_chain = max(max_chain, chain_lengths[word2])
		return max_chain


class Solution:

	def checkPre(self, small, large):
		i = 0
		j = -1
		while True:
			l = r = True
			if i < len(small) and small[i] == large[i]:
				i += 1
			else:
				l = False
			if j + len(small) >= 0 and small[j] == large[j]:
				j -= 1
			else:
				r = False
			if not l and (not r):
				break
		return i - j >= len(large)

	def longestStrChain(self, words: List[str]) -> int:
		table = dict()
		small = 10000
		large = 0
		for i in range(len(words)):
			length = len(words[i])
			if length not in table:
				small = min(length, small)
				large = max(length, large)
				table[length] = [i]
			else:
				table[length].append(i)
		pre = [1 for i in range(len(words))]
		for i in range(small, large):
			for j in range(len(table[i])):
				for k in range(len(table[i + 1])):
					if self.checkPre(words[table[i][j]], words[table[i + 1][k]]):
						pre[table[i + 1][k]] = max(pre[table[i + 1][k]], pre[table[i][j]] + 1)
		return max(pre)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words = set(words)
		dp = {}

		def chainEndingAt(word):
			if word not in words:
				return 0
			if word not in dp:
				chain_len = 1
				for i in range(len(word)):
					pred = word[:i] + word[i + 1:]
					chain_len = max(chain_len, chainEndingAt(pred) + 1)
				dp[word] = chain_len
			return dp[word]
		return max((chainEndingAt(word) for word in words))
		dp = {}
		for w in sorted(words, key=len):
			dp[w] = 1
			for i in range(len(w)):
				dp[w] = max(dp[w], dp.get(w[:i] + w[i + 1:], 0) + 1)
		return max(dp.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		visited = set()
		word_dict = {}
		for word in words:
			word_dict[word] = 1

		def visit(word):
			visited.add(word)
			for i in range(len(word)):
				child = word[:i] + word[i + 1:]
				if child not in word_dict:
					continue
				if child not in visited:
					visit(child)
				word_dict[word] = max(word_dict[word], 1 + word_dict[child])
		for word in words:
			visit(word)
		return max(word_dict.values())


class Solution:

	def match(self, small, big):
		mismatch = 0
		i = 0
		while i < len(small):
			j = i + mismatch
			if small[i] == big[j]:
				i += 1
				continue
			elif not mismatch:
				mismatch = 1
			elif mismatch == 1:
				return False
		return True

	def longestStrChain(self, words: List[str]) -> int:
		if len(words) == 1:
			return 1
		len_counts = {}
		min_len = 17
		for w in words:
			l = len(w)
			if l not in len_counts:
				len_counts[l] = [w]
				if l < min_len:
					min_len = l
			else:
				len_counts[l].append(w)
		chains = {}
		for w in len_counts[min_len]:
			chains[w] = 1
		ans = -1
		keys = sorted(list(len_counts.keys()))
		prev_len = keys[0]
		for l in keys[1:]:
			poss = len_counts[l]
			if l != prev_len + 1:
				prev_len = l
				for w in poss:
					if w not in chains:
						chains[w] = 1
				continue
			poss_last = len_counts[prev_len]
			for w in poss:
				if w not in chains:
					chains[w] = 1
				for last in poss_last:
					if self.match(last, w):
						chains[w] = max(chains[w], chains[last] + 1)
			prev_len = l
		return max(chains.values())


class Solution:

	def isPredecessor(self, s1, s2):
		if len(s2) - len(s1) != 1:
			return False
		newcharfound = False
		for i in range(len(s2)):
			if not newcharfound:
				if i == len(s1):
					return True
				if s1[i] != s2[i]:
					newcharfound = True
					j = i
			else:
				if s1[j] != s2[i]:
					return False
				j += 1
		return True

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		lentoword = collections.defaultdict(list)
		for (i, w) in enumerate(words):
			lentoword[len(w)].append((w, i))
		dp = [1 for i in range(len(words) + 1)]
		dp[0] = 0
		for i in range(1, len(words) + 1):
			word = words[i - 1]
			curlen = len(words[i - 1])
			for (nbor, nborindex) in lentoword[curlen - 1]:
				if self.isPredecessor(nbor, word):
					dp[i] = max(dp[i], dp[nborindex + 1] + 1)
		return max(dp)


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		word_dict = defaultdict(int)
		longest = 0
		for word in words:
			for i in range(len(word)):
				wc = word[:i] + word[i + 1:]
				word_dict[word] = max(word_dict[wc] + 1, word_dict[word])
			longest = max(longest, word_dict[word])
		return longest


class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		def dfs(cur):
			if cur not in s:
				return 0
			if len(cur) == 0:
				return 0
			if cur in d:
				return d[cur]
			res = 1
			for i in range(len(cur)):
				t = cur[:i] + cur[i + 1:]
				res = max(dfs(t) + 1, res)
			d[cur] = res
			return d[cur]
		s = set(words)
		d = {}
		_max = 0
		for w in words:
			_max = max(dfs(w), _max)
		return _max


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if len(words) == 0:
			return 0
		adj = {}
		for w in words:
			for i in range(len(w)):
				s = w[0:i] + w[i + 1:]
				if s not in adj:
					adj[s] = [w]
				else:
					adj[s].append(w)
		res = 1
		queue = []
		visited = {}

		def dfs(root):
			if root in visited:
				return visited[root]
			if root not in adj:
				visited[root] = 1
				return 1
			distance = 1
			for next_ in adj[root]:
				distance = max(distance, dfs(next_) + 1)
			visited[root] = distance
			return distance
		for w in words:
			length = dfs(w)
			res = max(res, length)
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = collections.defaultdict(int)
		for w in sorted(words, key=len):
			for i in range(len(w)):
				dp[w] = max(dp[w], 1 + dp[w[:i] + w[i + 1:]])
		return max(dp.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=len)
		graph = {}
		max_dist = 0
		for word in words:
			length = len(word)
			dist = 0
			for i in range(length):
				if (check := (word[:i] + word[i + 1:])) in graph:
					dist = max(graph[check], dist)
				graph[word] = dist + 1
				max_dist = max(max_dist, graph[word])
		return max_dist


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words = set(words)

		@lru_cache()
		def helper(word):
			if not word or word not in words:
				return 0
			return 1 + max((helper(word[:i] + word[i + 1:]) for i in range(len(word))))
		return max((helper(word) for word in words))


from functools import lru_cache

class Solution:

	def longestStrChain(self, words: List[str]) -> int:

		@lru_cache
		def chain_len(w):
			return 1 + max((chain_len(w[:i] + w[i + 1:]) for i in range(len(w)))) if w in valid else 0
		valid = set(words)
		return max((chain_len(w) for w in words))


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		ans = defaultdict(int)
		words.sort(key=len)
		for s in words:
			n = len(s)
			now = 0
			for i in range(n):
				(s1, s2) = (s[:i], s[i + 1:])
				now = max(now, ans[s1, s2])
			now += 1
			for i in range(n + 1):
				(s1, s2) = (s[:i], s[i:])
				ans[s1, s2] = now
		return max(ans.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		res = 0
		dic = collections.defaultdict(int)
		words.sort(key=lambda x: len(x))
		for w in words:
			m = len(w)
			for i in range(m):
				new = w[:i] + w[i + 1:]
				dic[w] = max(dic[w], dic[new] + 1)
			res = max(res, dic[w])
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		wc = {}
		for w in words:
			wc.setdefault(len(w), [])
			wc[len(w)].append(w)
		d = {}
		for i in sorted(wc.keys()):
			if i - 1 not in wc:
				for w in wc[i]:
					d[w] = 1
			else:
				for w in wc[i]:
					d[w] = 1
					for i in range(len(w)):
						if w[:i] + w[i + 1:] in d:
							d[w] = max(d[w], d[w[:i] + w[i + 1:]] + 1)
		return max(d.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		wordSet = set(words)
		i_min = min(wordSet)

		@lru_cache()
		def aux(word):
			if not word or word not in wordSet:
				return 0
			if len(word) == i_min:
				return 1
			return 1 + max((aux(word[:i] + word[i + 1:]) for i in range(len(word))))
		return max((aux(w) for w in words))


import copy

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words.sort(key=lambda word: len(word), reverse=True)
		wordSet = set(copy.deepcopy(words))
		visited = set()

		def find_chain(word, length):
			if word not in wordSet or word in visited:
				return length
			visited.add(word)
			max_len = 0
			for i in range(len(word)):
				tmp = copy.deepcopy(word)
				tmp = tmp[:i] + tmp[i + 1:]
				max_len = max(find_chain(tmp, length + 1), max_len)
			return max_len
		max_len = 0
		for word in words:
			max_len = max(max_len, find_chain(word, 0))
		return max_len


class Solution:

	def predecessor(self, word_1, word_2):
		if abs(len(word_1) - len(word_2)) != 1:
			return False
		idx_1 = 0
		idx_2 = 0
		while idx_1 < len(word_1) and idx_2 < len(word_2):
			if word_1[idx_1] != word_2[idx_2]:
				if idx_1 != idx_2:
					return False
				if len(word_1) < len(word_2):
					idx_2 += 1
				else:
					idx_1 += 1
			else:
				idx_1 += 1
				idx_2 += 1
		return True

	def longestStrChain(self, words: List[str]) -> int:
		dict = {}
		dp = [1 for i in range(0, len(words))]
		words.sort(key=len)
		for i in range(0, len(words)):
			words[i] = ''.join(sorted(words[i]))
			if len(words[i]) in list(dict.keys()):
				dict[len(words[i])].append(i)
			else:
				dict[len(words[i])] = [i]
		for i in range(0, len(words)):
			if len(words[i]) + 1 in list(dict.keys()):
				for elem in dict[len(words[i]) + 1]:
					if self.predecessor(words[elem], words[i]):
						dp[elem] = max(dp[elem], dp[i] + 1)
		ans = 0
		for i in range(0, len(dp)):
			ans = max(ans, dp[i])
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		from collections import defaultdict
		words.sort(key=lambda word: len(word), reverse=True)
		length = defaultdict(int)
		longest = 0
		for word in words:
			length[word] = max(length[word], 1)
			longest = max(longest, length[word])
			for i in range(len(word)):
				length[word[:i] + word[i + 1:]] = max(length[word[:i] + word[i + 1:]], length[word] + 1)
		return longest


from collections import defaultdict, deque

class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		words_set = set(words)

		def helper(word):
			if len(word) == 0:
				return 0
			for index in range(len(word)):
				string = word[:index] + word[index + 1:]
				if string not in maxChain and string in words_set:
					helper(string)
				maxChain[word] = max(maxChain[word], maxChain[string] + 1)
			return maxChain[word]
		maxChain = defaultdict(lambda : 0)
		for word in words:
			maxVal = 0
			if word not in maxChain:
				helper(word)
		return max(maxChain.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		dp = {}
		by_length = collections.defaultdict(set)
		for w in words:
			by_length[len(w)].add(w)
		for (i, l) in enumerate(sorted(by_length.keys())):
			if i == 0:
				for w in by_length[l]:
					dp[w] = 1
			elif not by_length[l - 1]:
				for w in by_length[l]:
					dp[w] = 1
			else:
				for w in by_length[l]:
					dp[w] = 1
					for j in range(len(w)):
						candidate = w[:j] + w[j + 1:]
						if candidate in by_length[l - 1]:
							dp[w] = max(dp[w], dp[candidate] + 1)
		return max(dp.values())


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		d = {j: 1 for j in words}
		n = len(words)
		used = {}
		c = [0]
		words = sorted(words, key=len)

		def dfs(s, l):
			if not s or s not in d:
				c[0] = max(c[0], len(l))
				return
			used[s] = 1
			m = 0
			for i in range(len(s)):
				dfs(s[:i] + s[i + 1:], l + [s])
				m = max(m, len(l))
		for i in range(n - 1, -1, -1):
			if words[i] not in used and c[0] < i:
				dfs(words[i], [])
		return c[0]


class Solution:

	def differ(self, x1, x2):
		(i, j) = (0, 0)
		diff = 0
		while i != len(x1) and j != len(x2):
			if x1[i] != x2[j]:
				diff += 1
			else:
				i += 1
			if diff > 1:
				return False
			j += 1
		return True

	def check(self, x1, x2):
		if x1 == x2:
			return True
		if abs(len(x1) - len(x2)) != 1:
			return False
		else:
			if len(x2) > len(x1):
				(a, b) = (x1, x2)
			else:
				(a, b) = (x2, x1)
			return self.differ(a, b)

	def longestStrChain(self, words: List[str]) -> int:
		words = list(set(words))
		lengths = {}
		for word in words:
			length = len(word)
			lengths[length] = lengths.get(length, []) + [word]
		lengths = sorted(lengths.items(), key=lambda x: x[0], reverse=True)
		value = {}
		max_chain = 1
		for (i, length) in enumerate(lengths):
			for word in length[1]:
				if i == 0:
					value[word] = 1
				else:
					temp_max = 0
					for temp_word in lengths[i - 1][1]:
						if self.check(word, temp_word):
							temp_max = max(temp_max, value[temp_word])
					value[word] = 1 + temp_max
					max_chain = max(value[word], max_chain)
		return max_chain


class Solution:

	def helper(self, memo, s, w):
		if w in memo:
			return memo[w]
		count = 0
		for i in range(len(w)):
			pre = w[:i] + w[i + 1:]
			if pre in s:
				count = max(count, self.helper(memo, s, pre))
		memo[w] = 1 + count
		return 1 + count

	def longestStrChain(self, words: List[str]) -> int:
		ans = 0
		memo = {}
		for w in words:
			ans = max(ans, self.helper(memo, set(words), w))
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		sets = collections.defaultdict(set)
		(n, dp) = (0, {})
		for word in words:
			n = max(n, len(word))
			sets[len(word)].add(word)
			dp[word] = 1
		ans = 1
		for i in reversed(list(range(2, n + 1))):
			if i - 1 not in sets:
				continue
			for word in sets[i]:
				for j in range(len(word)):
					new_word = word[:j] + word[j + 1:]
					if new_word in sets[i - 1]:
						dp[new_word] = dp[word] + 1
						ans = max(ans, dp[new_word])
		return ans


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		counter = collections.defaultdict(int)
		longest = 0
		for w in sorted(words, key=len):
			for i in range(len(w)):
				subword = w[:i] + w[i + 1:]
				count = counter[subword] + 1
				counter[w] = max(counter[w], count)
				longest = max(longest, counter[w])
		return longest


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		if not words:
			return 0
		words.sort(key=len)
		dp = [1 for _ in range(len(words))]
		start = collections.defaultdict(int)
		end = collections.defaultdict(int)
		for i in range(len(words) - 1, -1, -1):
			start[len(words[i])] = i
		if len(start) == 1:
			return 1
		for i in range(len(words)):
			end[len(words[i])] = i
		res = 1
		for i in range(start[len(words[0]) + 1], len(words)):
			for j in range(start[len(words[i]) - 1], end[len(words[i]) - 1] + 1):
				charA = set(words[j])
				charB = set(words[i])
				intersect = len(charA.intersection(charB))
				if intersect == len(charA):
					dp[i] = max(dp[i], dp[j] + 1)
			res = max(res, dp[i])
		return res


class Solution:

	def longestStrChain(self, words: List[str]) -> int:
		self.ans = 0
		words = sorted(words, key=lambda x: len(x))
		self.n = len(words)
		self.m = {}
		for i in range(self.n):
			if words[i] in self.m:
				self.m[words[i]] = i
			else:
				self.m[words[i]] = i
		for i in range(self.n - 1, -1, -1):
			self.findLongest(words, i, 0)
		return self.ans

	def findLongest(self, words, i, cur_ans):
		for j in range(len(words[i])):
			if words[i][:j] + words[i][j + 1:] in self.m:
				self.findLongest(words, self.m[words[i][:j] + words[i][j + 1:]], cur_ans + 1)
		self.ans = max(self.ans, cur_ans + 1)