Problem Statement

You are given a string s consisting of lowercase English letters.

If there is no 'a' in the string, return -1.

Example 1

Input

Code
s = "aaabcb"

Indexes

Code
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

Code
5

Example 2

Input

Code
s = "abcbzzd"

Indexes

Code
0 1 2 3 4 5 6
a b c b z z d
Code
a(0) → b(1) → c(2) → d(6)

Difference = 6

Output

Code
6

Example 3

Input

Code
xynjir

There is no 'a'.

Output

Code
-1

Brute Force Approach

For every 'a':

Complexity

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:

Code
reach(c) = reach(d)

Similarly,

Code
reach(b) = reach(c)
reach(a) = reach(b)

Data Structures Used

1. bestReach[]

Java
int[] bestReach = new int[26];

Purpose

Stores the maximum reachable index for every alphabet.

Example:

Initially,

-1 means the character has not been found yet.

2. reach[]

Java
int[] reach = new int[n];

Purpose

Stores:

From this index, what is the farthest index we can finally reach?

Example:

Code
reach[5] = 5
reach[2] = 6
reach[0] = 6

Dry Run

Consider:

Code
abcbzzd

Indexes

Code
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

Code
d

There is no 'e'.

So,

Code
reach[6] = 6

Update

Code
bestReach[d] = 6

Step 2

Index = 5

Character

Code
z

No next alphabet.

Code
reach[5] = 5

Update

Code
bestReach[z] = 5

Step 3

Index = 4

Character

Code
z

Again,

Code
reach[4] = 4

Update

Code
bestReach[z] = max(5, 4) = 5

Step 4

Index = 3

Character

Code
b

Need a 'c'.

We already know:

Code
bestReach[c] = 6

Therefore,

Code
reach[3] = 6

Update

Code
bestReach[b] = 6

Step 5

Index = 2

Character

Code
c

Need 'd'.

Code
bestReach[d] = 6

Therefore,

Code
reach[2] = 6

Update

Code
bestReach[c] = 6

Step 6

Index = 1

Character

Code
b

Need 'c'.

Code
bestReach[c] = 6

So,

Code
reach[1] = 6

Step 7

Index = 0

Character

Code
a

Need 'b'.

Code
bestReach[b] = 6

Therefore,

Code
reach[0] = 6

Answer

Code
6 - 0 = 6

Code Explanation

Java
int n = s.length();

Stores the string length.

Java
int[] bestReach = new int[26];

Stores the farthest reachable index for every alphabet.

Java
for (int i = 0; i < 26; i++)
    bestReach[i] = -1;

Initially, no alphabet has been seen.

Java
int[] reach = new int[n];

Stores the farthest index reachable from every position.

Java
int ans = -1;
boolean hasA = false;

Main Loop

Java
for (int i = n - 1; i >= 0; i--)

Traverse from right to left.

Current Character

Java
int c = s.charAt(i) - 'a';

Convert the character into an index.

Example:

Assume No Jump

Java
reach[i] = i;

Initially, assume this index cannot move anywhere.

Check Next Alphabet

Java
if (c < 25 && bestReach[c + 1] != -1)

Explanation

If the current character is not 'z' and the next alphabet exists on the right,

then:

Java
reach[i] = bestReach[c + 1];

Meaning the current character can reach wherever the next alphabet can reach.

Update bestReach

Java
bestReach[c] = Math.max(bestReach[c], reach[i]);

Store the farthest reachable index for this character.

Suppose two 'b' characters exist:

We store:

Code
8

because we always want the maximum.

Process Only 'a'

Java
if (c == 0)

Current character is 'a'.

Java
hasA = true;

Mark that 'a' exists.

Update the answer:

Java
ans = Math.max(ans, reach[i] - i);

Difference:

Code
Ending Index - Starting Index

Finally

Java
return hasA ? ans : -1;

If no 'a' exists, return:

Code
-1

Otherwise, return the maximum difference.

Complete Code

Java
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

ComplexityValue
Time ComplexityO(N)
Auxiliary SpaceO(1) (bestReach uses 26 elements. The reach array is O(N) and can be optimized if desired.)

Key Takeaways

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.