Given a string S which includes characters a, b, c, ..., z. Where value of a=1, b=2, ..., z=26. Now find the length of the largest increasing subsequence in the string.
Note:  Subsequence doesn't require elements to be consecutively increasing.
Example 1:
Input:
S = abcdapzfqh
Output:
6
Explanation:
The length of largest increasing
subsequence is 6. One of the
sequence with max length 6 is
a, b, c, d, p, z.
Example 2:
Input:
S = hkm 
Output:
3
Explanation:
The length of the largest increasing
subsequence is 3. Sequence with max
length 3 is h,k,m
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxLength() which take string S as input parameter and returns the length of the longest increasing subsequence.
Expected Time Complexity: O(|S|^{2}) 
Expected Space Complexity: O(|S|)
 
Constraints:
1<=|S|<=1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def maxLength(self,S): 

        # code here

Solutions:
from bisect import bisect_left

class Solution:

	def maxLength(self, S):
		arr = [S[0]]
		for item in S[1:]:
			if item > arr[-1]:
				arr.append(item)
			else:
				i = bisect_left(arr, item)
				arr[i] = item
		return len(arr)


class Solution:

	def maxLength(self, S):
		P = 'abcdefghijklmnopqrstuvwxyz'
		dp = [[-1 for i in range(len(P))] for j in range(len(S))]
		return self.helper(0, 0, S, P, dp)

	def helper(self, i, j, s1, s2, dp):
		if i == len(s1) or j == len(s2):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if s1[i] == s2[j]:
			dp[i][j] = 1 + self.helper(i + 1, j + 1, s1, s2, dp)
			return dp[i][j]
		else:
			dp[i][j] = max(self.helper(i + 1, j, s1, s2, dp), self.helper(i, j + 1, s1, s2, dp))
			return dp[i][j]


from bisect import bisect_left

class Solution:

	def maxLength(self, arr):
		longest = [arr[0]]
		for i in arr[1:]:
			if i > longest[-1]:
				longest.append(i)
			else:
				idx = bisect_left(longest, i)
				longest[idx] = i
		return len(longest)


class Solution:

	def maxLength(self, S):
		dp = [1] * len(S)
		m = 1
		for i in range(1, len(S)):
			for j in range(i):
				if S[j] < S[i]:
					dp[i] = max(dp[i], dp[j] + 1)
			m = max(m, dp[i])
		return m


class Solution:

	def maxLength(self, S):
		M = [1] * len(S)
		for i in range(1, len(S)):
			for j in range(0, i):
				if ord(S[i]) > ord(S[j]) and M[j] + 1 > M[i]:
					M[i] = M[j] + 1
		return max(M)


class Solution:

	def maxLength(self, S):
		arr = [S[0]]
		for item in S[1:]:
			if item > arr[-1]:
				arr.append(item)
			elif item <= arr[0]:
				arr[0] = item
			else:
				for i in range(len(arr)):
					if arr[i] < item <= arr[i + 1]:
						arr[i + 1] = item
		return len(arr)


class Solution:

	def maxLength(self, s):
		lst = []
		for i in s:
			lst.append(ord(i) - 97 + 1)
		n = len(lst)
		lis = []
		import bisect
		for i in range(n):
			ind = bisect.bisect_left(lis, lst[i])
			if ind >= len(lis):
				lis.append(lst[i])
			else:
				lis[ind] = lst[i]
		return len(lis)


from bisect import bisect_right as upper_bound

class Solution:

	def maxLength(self, s):
		n = len(s)
		dp = [float('inf')] * (n + 1)
		dp[0] = float('-inf')
		for i in range(n):
			x = upper_bound(dp, ord(s[i]))
			if dp[x - 1] < ord(s[i]):
				dp[x] = ord(s[i])
		for i in range(n, -1, -1):
			if dp[i] != float('inf'):
				return i


class Solution:

	def maxLength(self, S):
		n = len(S)
		lis = [1] * n
		for i in range(1, n):
			for j in range(i):
				if S[i] > S[j] and lis[i] < lis[j] + 1:
					lis[i] = lis[j] + 1
		maxi = 0
		for i in range(n):
			maxi = max(maxi, lis[i])
		return maxi


from bisect import bisect_left

class Solution:

	def maxLength(self, S):
		if not S:
			return 0
		tail = [chr(0)] * (len(S) + 1)
		count = 1
		tail[0] = S[0]
		for i in range(1, len(S)):
			if ord(S[i]) > ord(tail[count - 1]):
				tail[count] = S[i]
				count += 1
			else:
				tail[bisect_left(tail, S[i], 0, count - 1)] = S[i]
		return count


from bisect import bisect_left as BL

class Solution:

	def maxLength(self, S):
		dp = []
		for c in S:
			pos = BL(dp, c)
			if pos < len(dp):
				dp[pos] = c
			else:
				dp.append(c)
		return len(dp)


class Solution:

	def ceil_fun(self, table, element, l, r):
		while l < r:
			m = (r + l) // 2
			if l + 1 == r:
				if table[m] >= element:
					return l
				else:
					return r
			if element <= table[m]:
				r = m
			else:
				l = m + 1
		return r

	def maxLength(self, S):
		n = len(S)
		table = [0 for i in range(n)]
		table[0] = S[0]
		count = 1
		for i in range(1, n):
			if S[i] < table[0]:
				table[0] = S[i]
			elif S[i] > table[count - 1]:
				table[count] = S[i]
				count += 1
			else:
				index = self.ceil_fun(table, S[i], 0, count - 1)
				table[index] = S[i]
		return count


class Solution:

	def maxLength(self, S):
		res = []
		for i in S:
			res.append(ord(i) - 97 + 1)
		dp = [0 for i in range(len(res))]
		for i in range(0, len(res)):
			maxi = 0
			for j in range(0, i):
				if res[i] > res[j]:
					maxi = max(maxi, dp[j])
			dp[i] = 1 + maxi
		return max(dp)


class Solution:

	def maxLength(self, S):
		T = sorted(list(set(list(S))))
		dp = [[0] * (len(S) + 1) for _ in range(1 + len(T))]
		for i in range(1, len(T) + 1):
			for j in range(1, len(S) + 1):
				if S[j - 1] == T[i - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[-1][-1]


def ceil(arr, left, right, ele):
	c = -1
	while left <= right:
		mid = (left + right) // 2
		if arr[mid] > ele:
			c = mid
			right = mid - 1
		elif arr[mid] < ele:
			left = mid + 1
		else:
			return mid
	return c

def LIS(arr):
	res = []
	res.append(arr[0])
	for i in range(1, len(arr)):
		if res[-1] < arr[i]:
			res.append(arr[i])
		else:
			k = ceil(res, 0, len(res), arr[i])
			res[k] = arr[i]
	return res

class Solution:

	def maxLength(self, S):
		return len(LIS([ord(i) for i in S]))


import bisect

class Solution:

	def maxLength(self, arr):
		n = len(arr)
		seq = [0 for i in range(n + 1)]
		seq
		length = 1
		seq[0] = arr[0]
		for i in range(1, n):
			if arr[i] > seq[length - 1]:
				seq[length] = arr[i]
				length += 1
			else:
				pos = bisect.bisect_left(seq, arr[i], 0, length - 1)
				seq[pos] = arr[i]
		return length


class Solution:

	def maxLength(self, S):
		data = [0] * len(S)
		for i in range(len(S)):
			data[i] = ord(S[i]) - 96
		dp = [1] * len(S)
		ans = -1
		for i in range(len(S)):
			for j in range(0, i):
				if S[i] > S[j]:
					dp[i] = max(dp[i], 1 + dp[j])
			ans = max(ans, dp[i])
		return ans


class Solution:

	def maxLength(self, S):
		p = [1] * len(S)
		for i in range(len(S)):
			for j in range(i):
				if S[i] > S[j] and p[i] < p[j] + 1:
					p[i] = p[j] + 1
		return max(p)


class Solution:

	def maxLength(self, S):
		S = list(S)
		lis = [1] * len(S)
		for i in range(len(S) - 1, -1, -1):
			for j in range(i + 1, len(S)):
				if ord(S[i]) < ord(S[j]):
					lis[i] = max(lis[i], 1 + lis[j])
		return max(lis)


class Solution:

	def ceilBinarySearchIndex(self, dp, low, high, key):
		while low < high:
			mid = low + (high - low) // 2
			if dp[mid] >= key:
				high = mid
			else:
				low = mid + 1
		return high

	def maxLength(self, S):
		n = len(S)
		dp = [0] * n
		dp[0] = S[0]
		ind = 1
		for i in range(1, n):
			if dp[ind - 1] < S[i]:
				dp[ind] = S[i]
				ind += 1
			else:
				bsi = self.ceilBinarySearchIndex(dp, 0, ind - 1, S[i])
				dp[bsi] = S[i]
		return ind


from bisect import bisect_left

class Solution:

	def maxLength(self, s):
		st = []
		for i in s:
			if not st or ord(i) > st[-1]:
				st.append(ord(i))
			else:
				idx = bisect_left(st, ord(i))
				st[idx] = ord(i)
		return len(st)


class Solution:

	def maxLength(self, S):
		N = len(S)
		dp = [0] * N
		Omax = 0
		for i in range(N):
			max_len = 0
			for j in range(i):
				if ord(S[i]) > ord(S[j]):
					max_len = max(max_len, dp[j])
			dp[i] = max_len + 1
			Omax = max(Omax, dp[i])
		return Omax
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.maxLength(S))


class Solution:

	def maxLength(self, arr):
		n = len(arr)
		dp = [1 for i in range(n)]
		for i in range(1, n):
			maxi = 0
			for j in range(i):
				if ord(arr[i]) > ord(arr[j]):
					maxi = max(maxi, dp[j])
			dp[i] = maxi + 1
		return max(dp)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.maxLength(S))


class Solution:

	def maxLength(self, S):
		ans = 1
		n = len(S)
		dp = [1] * n
		for i in range(n):
			for j in range(0, i):
				if S[i] > S[j]:
					dp[i] = max(dp[i], dp[j] + 1)
					ans = max(dp[i], ans)
		return ans


class Solution:

	def maxLength(self, S):
		dp = []
		n = len(S)
		for i in range(n):
			if len(dp) == 0:
				dp.append(S[i])
			elif S[i] > dp[-1]:
				dp.append(S[i])
			else:
				idx = self.bsearch(dp, S[i])
				dp[idx] = S[i]
		return len(dp)

	def bsearch(self, dp, c):
		(l, r) = (0, len(dp) - 1)
		while l < r:
			mid = l + (r - l) // 2
			if dp[mid] < c <= dp[mid + 1]:
				return mid + 1
			elif dp[mid] >= c > dp[mid - 1]:
				return mid
			elif dp[mid] < c:
				l = mid + 1
			else:
				r = mid - 1
		return 0


import bisect

class Solution:

	def maxLength(self, S):
		n = len(S)
		ans = [S[0]]
		for i in range(1, n):
			if S[i] > ans[-1]:
				ans.append(S[i])
			else:
				index = bisect.bisect_left(ans, S[i])
				ans[index] = S[i]
		return len(ans)


class Solution:

	def lcs(self, s1, s2):
		(m, n) = (len(s1), len(s2))
		t = [[0 for j in range(n + 1)] for i in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if s1[i - 1] == s2[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return t[m][n]

	def maxLength(self, s):
		s2 = list(set(list(s)))
		s2.sort()
		return self.lcs(list(s), s2)


from bisect import bisect, bisect_left

class Solution:

	def maxLength(self, a):
		ans = [a[0]]
		for i in range(1, len(a)):
			if ans[-1] < a[i]:
				ans.append(a[i])
			elif ans[0] > a[i]:
				ans[0] = a[i]
			else:
				k = bisect_left(ans, a[i])
				ans[k] = a[i]
		return len(ans)


class Solution:

	def maxLength(self, S):
		a = S
		n = len(a)
		b = sorted(list(set(a)))
		m = len(b)
		dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif a[i - 1] == b[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[n][m]


class Solution:

	def maxLength(self, arr):
		n = len(arr)
		dp = [0] * n
		overall_max = 0
		for i in range(n):
			maxm = 0
			for j in range(0, i):
				if arr[i] > arr[j]:
					if dp[j] > maxm:
						maxm = dp[j]
			dp[i] = maxm + 1
			if dp[i] > overall_max:
				overall_max = dp[i]
		return overall_max


class Solution:

	def maxLength(self, arr):
		n = len(arr)
		out = [1] * n
		for i in range(1, n):
			for j in range(i):
				if arr[i] > arr[j]:
					out[i] = max(out[i], out[j] + 1)
		return max(out)


class Solution:

	def maxLength(self, s):
		n = len(s)
		table = [0 for i in range(n + 1)]
		length = 0
		table[0] = s[0]
		length = 1
		for i in range(1, n):
			if s[i] < table[0]:
				table[0] = s[i]
			elif s[i] > table[length - 1]:
				table[length] = s[i]
				length += 1
			else:
				table[self.binarySearch(table, -1, length - 1, s[i])] = s[i]
		return length

	def binarySearch(self, table, l, r, key):
		while r - l > 1:
			mid = l + (r - l) // 2
			if table[mid] >= key:
				r = mid
			else:
				l = mid
		return r


class Solution:

	def maxLength(self, S):
		n = len(S)
		dp = [1] * n
		for i in range(1, n):
			for j in range(i):
				if ord(S[i]) - ord('a') > ord(S[j]) - ord('a') and dp[i] < dp[j] + 1:
					dp[i] = dp[j] + 1
		return max(dp[0:])


class Solution:

	def maxLength(self, s):
		n = len(s)
		dp = [1 for i in range(n)]
		for i in range(1, n):
			for j in range(0, i):
				if ord(s[i]) > ord(s[j]):
					dp[i] = max(dp[i], dp[j] + 1)
		res = 0
		for i in range(0, n):
			res = max(res, dp[i])
		return res


import bisect

class Solution:

	def maxLength(self, s):
		sub = []
		for c in s:
			i = bisect.bisect_left(sub, c)
			if i == len(sub):
				sub.append(c)
			else:
				sub[i] = c
		return len(sub)


from bisect import bisect_left as bis

class Solution:

	def maxLength(self, arr):
		n = len(arr)
		if n == 1:
			return 1
		dp = [0] * n
		dp[0] = arr[0]
		l = 1
		for i in arr[1:]:
			if i < dp[0]:
				dp[0] = i
			elif i > dp[l - 1]:
				dp[l] = i
				l += 1
			else:
				dp[bis(dp, i, 0, l - 1)] = i
		return l


class Solution:

	def binary_search(self, arr, key):
		l = 0
		h = len(arr) - 1
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] == key:
				return mid
			if key < arr[mid]:
				h = mid - 1
			else:
				l = mid + 1
		return l

	def maxLength(self, S):
		top_table = [S[0]]
		for i in range(1, len(S)):
			key = S[i]
			ip = self.binary_search(top_table, key)
			if ip == len(top_table):
				top_table.append(key)
			else:
				top_table[ip] = key
		return len(top_table)


class Solution:

	def maxLength(self, S):
		best = [1] * len(S)
		for i in range(1, len(S)):
			best_so_far = 1
			for j in range(0, i):
				if S[j] < S[i]:
					best_so_far = max(best_so_far, best[j] + 1)
			best[i] = best_so_far
		return max(best)


class Solution:

	def ceilSearch(self, A, l, h, key):
		while l <= h:
			if key <= A[l]:
				return l
			if key > A[h]:
				return -1
			mid = (l + h) // 2
			if A[mid] == key:
				return mid
			elif mid - 1 >= 0 and A[mid] > key and (A[mid - 1] < key):
				return mid
			elif A[mid] < key:
				l = mid + 1
			else:
				h = mid - 1
		return -1

	def maxLength(self, S):
		A = list(S)
		seq = [A[0]]
		for i in range(1, len(A)):
			if A[i] > seq[-1]:
				seq.append(A[i])
			elif A[i] < seq[-1]:
				ind = self.ceilSearch(seq, 0, len(seq) - 1, A[i])
				seq[ind] = A[i]
		return len(seq)


class Solution:

	def CeilIndex(self, A, l, r, key):
		while r - l > 1:
			m = l + (r - l) // 2
			if A[m] >= key:
				r = m
			else:
				l = m
		return r

	def maxLength(self, S):
		A = list(S)
		size = len(A)
		tailTable = [0 for i in range(size + 1)]
		l = 0
		tailTable[0] = A[0]
		l = 1
		for i in range(1, size):
			if A[i] < tailTable[0]:
				tailTable[0] = A[i]
			elif A[i] > tailTable[l - 1]:
				tailTable[l] = A[i]
				l += 1
			else:
				tailTable[self.CeilIndex(tailTable, -1, l - 1, A[i])] = A[i]
		return l


class Solution:

	def maxLength(self, S):
		lengths = [1] * len(S)
		for i in range(len(S)):
			for j in range(len(S)):
				if j > i:
					break
				if S[i] > S[j]:
					lengths[i] = max(lengths[i], lengths[j] + 1)
		return max(lengths)


class Solution:

	def maxLength(self, S):
		l = list(S)
		dp = [1 for i in range(len(l))]
		for i in range(1, len(l)):
			for j in range(0, i):
				if l[j] < l[i]:
					dp[i] = max(dp[i], dp[j] + 1)
		return max(dp)