Maximum Reachable Index Difference

Problem Overview

You may start only at an index containing a.

Intuition

You may start only at an index containing a. Each jump moves right to the immediate next letter in the alphabet (a→b→c…). The goal is the largest endingIndex − startingIndex over any valid jump chain. While scanning left to right, keep the earliest start index that can reach each letter — when you see c, the best start for that chain is the same as for b one step earlier.

Algorithm

1Maintain minStart[26], filled with ∞, where minStart[c] is the smallest index that can start a valid chain ending at letter c.
2For each index i with character ch at position idx = ch − a:
3 • If idx == 0: set minStart[0] = min(minStart[0], i) (only a can start).
4 • Else if minStart[idx − 1] is known: set minStart[idx] = min(minStart[idx], minStart[idx − 1]) and update ans = max(ans, i − minStart[idx]).
5Return ans (stays −1 if no chain longer than a single a exists).

Example Walkthrough

Input: s = "abzc"

1. i=0, a: minStart[a]=0, ans=0.
2. i=1, b: minStart[b]=0, ans=max(0,1−0)=1.
3. i=2, z: needs y — minStart[y] is unknown, skip.
4. i=3, c: minStart[c]=0, ans=max(1,3−0)=3.

Output: 3

Common Pitfalls

• Starting index must be a — do not treat every character as a valid start.
• Jumps require the exact next letter; skipping letters (a then c) is invalid.
• Propagate minStart[idx] from minStart[idx−1], not from the previous index in the string.
• Return −1 when no valid chain exists (e.g. string has no a).

Maximum Reachable Index Difference.java

Java


import java.util.*;

class Solution {

    // Approach: Start only at 'a'. From each position jump right to the next
    // alphabet letter (a→b→c…). Track minStart[c] = earliest index that can
    // begin a valid chain ending at letter c. When s[i] is letter c, extend from
    // minStart[c-1] and maximize i - minStart[c]. Return -1 if no 'a' exists.
    // Complexity: O(n) time and O(1) space (26-letter table).
    public int maxIndexDifference(String s) {
        int[] minStart = new int[26];
        Arrays.fill(minStart, Integer.MAX_VALUE);
        int maxDiff = -1;

        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if (idx == 0) {
                minStart[0] = Math.min(minStart[0], i);
                maxDiff = Math.max(maxDiff, 0);
            } else {
                if (minStart[idx - 1] != Integer.MAX_VALUE) {
                    minStart[idx] = Math.min(minStart[idx], minStart[idx - 1]);
                    maxDiff = Math.max(maxDiff, i - minStart[idx]);
                }
            }
        }
        return maxDiff;
    }
}

Was this solution helpful?