Stack-Based Index Tracking

Calculating the maximum length of well-formed parenthesis substrings requires maintaining a dynamic baseline for distance measurements. A stack storing character indices provides an efficient mechanism for this. Initialize the data structure with -1 to act as a virtual boundary before the string begins. Process the input sequentially:

• Upon encountering an opening bracket (, store its index.
• Upon encountering a closing bracket ), remove the top index. If the stack empties, the current closing bracket lacks a match; push its index to establish a new baseline. If elements remain, a valid pair is identified. Compute the substring length by subtracting the current top index from the present position, updating the maximum recorded length when necessary.

import java.util.ArrayDeque;
import java.util.Deque;

public class ValidParenthesesSolver {
    public int computeMaxLength(String sequence) {
        if (sequence == null || sequence.isEmpty()) {
            return 0;
        }

        int peakLength = 0;
        Deque<Integer> boundaryTracker = new ArrayDeque<>();
        boundaryTracker.push(-1);

        char[] chars = sequence.toCharArray();
        for (int pos = 0; pos < chars.length; pos++) {
            if (chars[pos] == '(') {
                boundaryTracker.push(pos);
            } else {
                boundaryTracker.pop();
                if (boundaryTracker.isEmpty()) {
                    boundaryTracker.push(pos);
                } else {
                    int currentSpan = pos - boundaryTracker.peek();
                    peakLength = Math.max(peakLength, currentSpan);
                }
            }
        }
        return peakLength;
    }
}

Dynamic Programming State Transition

A linear scan can also populate a state array where dp[k] denotes the length of the longest valid substring terminating at index k. Initialize the array with zeros and iterate from the second character onward. Transitions depend on the current and preceding characters:

• Adjacent Pair Formation: When s[k] is ) and s[k-1] is (, a direct match occurs. The state updates to 2 plus any valid length ending at k-2 (handling boundary conditions).
• Nested Structure Closure: When both s[k] and s[k-1] are ), the algorithm checks for a macthing opening bracket preceding the inner valid block. Calculate the target index as target = k - dp[k-1] - 1. If target is within bounds and holds (, the current state becomes dp[k-1] + 2. To account for concatenated valid sequences, add dp[target - 1] if target > 0.

Continuously track the highest value generated in the state array.

public class ValidParenthesesSolver {
    public int computeMaxLengthDP(String sequence) {
        if (sequence == null || sequence.length() < 2) {
            return 0;
        }

        char[] tokens = sequence.toCharArray();
        int[] spanRecord = new int[tokens.length];
        int optimalResult = 0;

        for (int k = 1; k < tokens.length; k++) {
            if (tokens[k] != ')') continue;

            if (tokens[k - 1] == '(') {
                spanRecord[k] = (k >= 2 ? spanRecord[k - 2] : 0) + 2;
            } else {
                int innerSpan = spanRecord[k - 1];
                int openerIdx = k - innerSpan - 1;

                if (openerIdx >= 0 && tokens[openerIdx] == '(') {
                    spanRecord[k] = innerSpan + 2;
                    if (openerIdx > 0) {
                        spanRecord[k] += spanRecord[openerIdx - 1];
                    }
                }
            }
            optimalResult = Math.max(optimalResult, spanRecord[k]);
        }
        return optimalResult;
    }
}