Problem Statement
You are given a string s consisting of lowercase English letters.
You can start only from an index containing 'a'.
From the current character, you can jump to any index on the right that contains the next alphabet.
'a' → 'b'
'b' → 'c'
'c' → 'd'
and so on.
Continue jumping until no further jump is possible.
Find the maximum difference between the starting index and the ending index.
If there is no 'a' in the string, return -1.
Example 1
Input
s = "aaabcb"
Indexes
0 1 2 3 4 5
a a a b c b
Start at index 0 ('a')
Jump directly to index 5 ('b')
Difference = 5 - 0 = 5
Output
5
Example 2
Input
s = "abcbzzd"
Indexes
0 1 2 3 4 5 6
a b c b z z d
a(0) → b(1) → c(2) → d(6)
Difference = 6
Output
6
Example 3
Input
xynjir
There is no 'a'.
Output
-1
Brute Force Approach
For every 'a':
Search every possible 'b'.
From every 'b', search every 'c'.
Continue until no jump exists.
Complexity
Time: O(N²) or worse
Space: O(1)
This is too slow for N = 100000.
Optimized Idea (Right to Left)
Instead of searching forward every time, process the string from right to left.
While moving from right to left, we already know the farthest place every character can reach.
This avoids repeated searching.
Main Observation
Suppose we are currently at character 'c'.
To move further, we only need to know:
What is the farthest reachable index from any 'd' present on the right?
If we already know that:
reach(c) = reach(d)
Similarly,
reach(b) = reach(c)
reach(a) = reach(b)
Data Structures Used
1. bestReach[]
int[] bestReach = new int[26];
Purpose
Stores the maximum reachable index for every alphabet.
Example:
bestReach[0] → 'a'
bestReach[1] → 'b'
bestReach[2] → 'c'
...
bestReach[25] → 'z'
Initially,
-1 means the character has not been found yet.
2. reach[]
int[] reach = new int[n];
Purpose
Stores:
From this index, what is the farthest index we can finally reach?
Example:
reach[5] = 5
reach[2] = 6
reach[0] = 6
Dry Run
Consider:
abcbzzd
Indexes
0 1 2 3 4 5 6
a b c b z z d
We traverse from right to left.
Step 1
Index = 6
Character
d
There is no 'e'.
So,
reach[6] = 6
Update
bestReach[d] = 6
Step 2
Index = 5
Character
z
No next alphabet.
reach[5] = 5
Update
bestReach[z] = 5
Step 3
Index = 4
Character
z
Again,
reach[4] = 4
Update
bestReach[z] = max(5, 4) = 5
Step 4
Index = 3
Character
b
Need a 'c'.
We already know:
bestReach[c] = 6
Therefore,
reach[3] = 6
Update
bestReach[b] = 6
Step 5
Index = 2
Character
c
Need 'd'.
bestReach[d] = 6
Therefore,
reach[2] = 6
Update
bestReach[c] = 6
Step 6
Index = 1
Character
b
Need 'c'.
bestReach[c] = 6
So,
reach[1] = 6
Step 7
Index = 0
Character
a
Need 'b'.
bestReach[b] = 6
Therefore,
reach[0] = 6
Answer
6 - 0 = 6
Code Explanation
int n = s.length();
Stores the string length.
int[] bestReach = new int[26];
Stores the farthest reachable index for every alphabet.
for (int i = 0; i < 26; i++)
bestReach[i] = -1;
Initially, no alphabet has been seen.
int[] reach = new int[n];
Stores the farthest index reachable from every position.
int ans = -1;
boolean hasA = false;
Main Loop
for (int i = n - 1; i >= 0; i--)
Traverse from right to left.
Current Character
int c = s.charAt(i) - 'a';
Convert the character into an index.
Example:
Assume No Jump
reach[i] = i;
Initially, assume this index cannot move anywhere.
Check Next Alphabet
if (c < 25 && bestReach[c + 1] != -1)
Explanation
If the current character is not 'z' and the next alphabet exists on the right,
then:
reach[i] = bestReach[c + 1];
Meaning the current character can reach wherever the next alphabet can reach.
Update bestReach
bestReach[c] = Math.max(bestReach[c], reach[i]);
Store the farthest reachable index for this character.
Suppose two 'b' characters exist:
First reaches 8
Second reaches 5
We store:
8
because we always want the maximum.
Process Only 'a'
if (c == 0)
Current character is 'a'.
hasA = true;
Mark that 'a' exists.
Update the answer:
ans = Math.max(ans, reach[i] - i);
Difference:
Ending Index - Starting Index
Finally
return hasA ? ans : -1;
If no 'a' exists, return:
-1
Otherwise, return the maximum difference.
Complete Code
class Solution {
public int maxIndexDifference(String s) {
int n = s.length();
int[] bestReach = new int[26];
for (int i = 0; i < 26; i++)
bestReach[i] = -1;
int[] reach = new int[n];
int ans = -1;
boolean hasA = false;
for (int i = n - 1; i >= 0; i--) {
int c = s.charAt(i) - 'a';
// By default, assume we cannot jump further.
reach[i] = i;
// If the next alphabet exists on the right,
// inherit its farthest reachable index.
if (c < 25 && bestReach[c + 1] != -1) {
reach[i] = bestReach[c + 1];
}
// Update the best reachable index for this character.
bestReach[c] = Math.max(bestReach[c], reach[i]);
// Only 'a' can be a starting point.
if (c == 0) {
hasA = true;
ans = Math.max(ans, reach[i] - i);
}
}
return hasA ? ans : -1;
}
}
Complexity Analysis
| Complexity | Value |
|---|
| Time Complexity | O(N) |
| Auxiliary Space | O(1) (bestReach uses 26 elements. The reach array is O(N) and can be optimized if desired.) |
Key Takeaways
Traverse the string from right to left.
bestReach[] remembers the farthest reachable index for each alphabet.
reach[] stores the farthest index reachable from each position.
For every 'a', compute reach[i] - i and keep the maximum.
This avoids repeated forward searches, giving an efficient O(N) solution.
Summary
The brute-force approach repeatedly searches forward for the next alphabet, resulting in quadratic time complexity. By traversing the string from right to left, we can reuse previously computed information about the farthest reachable positions. The bestReach[] array stores the best reachable index for each alphabet, while reach[] records the farthest destination from every position. This dynamic programming approach eliminates redundant searches and computes the maximum index difference for all valid starting 'a' characters in O(N) time, making it efficient even for very large input strings.
Join the conversation! Your thoughts help the community grow.