Given a string S containing lowercase English alphabets. Initially, you are at index 1. You can only jump to some other location j (j>i) only if s[j] = s[i] + 1. Find the maximum index you can reach.
Note: First character of the string is always 'a'. He can only go 'a'->'b','b'->'c','c'->'d' and so on. 'a'->'c','b'->'d','b'->'a' is not a valid move. He can start from any of index of 'a'. Indexing is zero based.
 
Example 1:
Input:
s = "aaabbcdbdt"
Output:
8
Explanation:
One can start from 'a' at index 0 or 1 
or 2 and then move to 'b' at index 3 or 
4, then jump to 'c' at index 5 and then 
go to  'd' at greater index than 6 which 
is 8. Thus the answer is 8.
 
Example 2:
Input:
s = "aabcb"
Output:
4
Explanation:
Again one can starts from 'a' and proceed 
to 'b' and then 'c'. But we have 'b' at 
the highest index also, so he will not go 
to 'c' and from 'a', we will directly jump 
to 'b'.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function maximum_index() which takes the string S as an input parameter and returns the maximum index where one can reach.
 
Expected Time Complexity: O(|S|)
Expected Space Complexity: O(1)
 
Constraints:
1 <= size of string <= 100000

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3


class Solution:
    def maximum_index(self, s):
        # Code here

Solutions:
class Solution:

	def maximum_index(self, s):
		prev = 'a'
		ans = 0
		for i in range(1, len(s)):
			if ord(s[i]) == ord(prev) + 1:
				prev = s[i]
				ans = i
			elif ord(s[i]) <= ord(prev):
				ans = i
		return ans


class Solution:

	def maximum_index(self, s):
		n = len(s)
		prev_val = s[0]
		max_index = 0
		for i in range(1, n):
			if ord(s[i]) - ord(prev_val) == 1:
				prev_val = s[i]
				max_index = i
			elif ord(s[i]) <= ord(prev_val):
				max_index = i
		return max_index


from collections import defaultdict

class Solution:

	def maximum_index(self, s):
		n = len(s)
		p = 'a'
		ans = 0
		for i in range(n):
			if ord(s[i]) == ord(p) + 1:
				p = s[i]
				ans = i
			elif ord(s[i]) <= ord(p):
				ans = i
		return ans
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		s = input()
		ob = Solution()
		ans = ob.maximum_index(s)
		print(ans)