Given a String S (in lowerCase only). Starting from letter 'a' which is the only source. for example:- "aaabcahd..." . Now you can only jump from one character to another in the form that a to b; b to c; c to d and so on. You have to find the maximum distance from source to destination. And if there is no place to jump on then print -1.
 
Example 1:
Input: aaabcb
Output: 6
Explanation: As 'a' will only jump to 'b' 
and the maximum distance will is 6.
Example 2:
Input: aabac
Output: 5
Explanation: As 'a' will only jump to 'b' 
and 'b' will jump to 'c' and distance 
is 5.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maximum_distance() which takes the string S as input parameter and returns the maximum distance. If not possible to reach at destination then return -1.
Expected Time complexity: O(n)
Expected Space complexity: O(n)
 
Constraints:
1 <= size of string <= 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3


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

Solutions:
class Solution:

	def maximum_distance(self, s):
		if not 'a' in s:
			return -1
		n = len(s)
		r = s[::-1]
		output = -1
		j = s.index('a')
		for i in range(25):
			temp = s[j:]
			if not chr(i + 98) in temp:
				return output
			output = max(output, n - r.index(chr(i + 98)))
			j = j + temp.index(chr(i + 98))
		return output


class Solution:

	def maximum_distance(self, s):
		a = set()
		a.add('a')
		m = -1
		for i in range(len(s)):
			if chr(ord(s[i]) - 1) in a:
				a.add(s[i])
				m = max(m, i + 1)
		return m