Definition
- Longest Valid Parentheses – finds the length of the longest contiguous substring of round brackets that is correctly balanced.
- Index stack – stores indices rather than characters, seeded with -1 as a base marker representing the position just before the string.
- On '(' – push the index onto the stack.
- On ')' – pop the top, then if the stack is empty push the current index as a new base, otherwise compute the length as the current index minus the new stack top.
- Base marker – the bottom of the stack always holds the most recent position that broke validity, enabling correct length calculation.
- Complexity – O(n) time with one scan and O(n) space for the stack.
The National Bank of India has a long string of grouping markers from a partially corrupted fee formula and wants to find the longest unbroken balanced stretch for salvage parsing. Think of keeping a stack of positions. When you open a bracket, you note its position. When you close one, you pair it off and measure how long the balanced run now extends from here back to the last broken position. The widest such run is the answer.
Understanding the Concepts
What is the Longest Valid Parentheses problem?
Unlike the simple validity check that returns true or false, this problem asks for the length of the longest contiguous substring that is correctly balanced. For example, in ")()())" the longest valid run is "()()" with length 4. The key difference from plain validation is that you need to track positions, not just whether brackets match.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class LongestValidParentheses {
public static int longestValid(String s) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1); // base marker
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i); // new base marker
} else {
maxLen = Math.max(maxLen, i - stack.peek());
}
}
}
return maxLen;
}
public static void main(String[] args) {
System.out.println(longestValid(")()())")); // 4
System.out.println(longestValid("()(()")); // 2
System.out.println(longestValid("(()")); // 2
}
}
4
2
2
Why does this problem use an index stack instead of a character stack?
The character stack in plain validation only tells you whether brackets match. Here you need the length of the balanced run, which requires knowing the starting position. By storing indices, you can compute the length as the difference between the current index and the boundary index. The base marker at -1 represents the position just before the string, so the first valid run starting at index 0 is measured correctly.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class WhyIndices {
public static void main(String[] args) {
String s = "(()";
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1); // base at position -1
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
System.out.println("i=" + i + ": push index " + i + " -> stack " + stack);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
System.out.println("i=" + i + ": new base " + i);
} else {
int len = i - stack.peek();
System.out.println("i=" + i + ": valid run length = " + i + " - " + stack.peek() + " = " + len);
}
}
}
}
}
i=0: push index 0 -> stack [0, -1]
i=1: push index 1 -> stack [1, 0, -1]
i=2: valid run length = 2 - 0 = 2
How does the base marker work?
The base marker is the heart of this algorithm. The bottom of the stack always holds the index of the most recent position that broke validity. Initially it is -1, meaning nothing has broken yet. When an unmatched ) appears (the stack empties after a pop), that ) becomes the new base marker because it is an unclosable position. The length of a valid run is always the current index minus this base.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class BaseMarkerDemo {
public static void main(String[] args) {
String s = ")()())"; // longest valid is "()()" = 4
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
int max = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i); // unmatched ')' becomes new base
System.out.println("i=" + i + ": new base marker");
} else {
int len = i - stack.peek();
max = Math.max(max, len);
System.out.println("i=" + i + ": run length=" + len + ", max=" + max);
}
}
}
System.out.println("Answer: " + max);
}
}
i=0: new base marker
i=1: run length=0, max=0
i=2: run length=2, max=2
i=3: run length=0, max=2
i=4: run length=4, max=4
i=5: new base marker
Answer: 4
Why must you pop before measuring?
When you meet a ), you first pop the matching ( index from the stack. The new top after the pop is the boundary of the enclosing valid run. If you measured before popping, you would count the matched opener's index in the length, producing an off-by-one error. The pop-then-measure order is what makes the arithmetic correct.
package com.bank.core;
public class PopBeforeMeasure {
public static void main(String[] args) {
// For string "(())", when we reach index 3 ')'
// Stack before: [1, 0, -1] (index 1 is the matched '(')
// Pop index 1: stack becomes [0, -1]
// New top is 0, length = 3 - 0 = 3 ... but wait
// Actually at index 2 ')' we pop index 1, new top is 0
// length = 2 - 0 = 2. Then at index 3 ')' we pop 0,
// new top is -1, length = 3 - (-1) = 4. Correct!
System.out.println("Pop-then-measure gives correct length 4 for '(())'.");
System.out.println("Measure-then-pop would give length 3 at index 3, which is wrong.");
}
}
Pop-then-measure gives correct length 4 for '(())'.
Measure-then-pop would give length 3 at index 3, which is wrong.
What are the edge cases?
An empty string returns 0. A string of all openers or all closers returns 0 because no pair can form. A fully balanced string like "(())()" returns its full length. Adjacent valid runs like "()()" are captured correctly because the base marker persists across consecutive pairs.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class LVPEdgeCases {
public static int longestValid(String s) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
int max = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') { stack.push(i); }
else {
stack.pop();
if (stack.isEmpty()) stack.push(i);
else max = Math.max(max, i - stack.peek());
}
}
return max;
}
public static void main(String[] args) {
System.out.println("Empty: " + longestValid("")); // 0
System.out.println("All open: " + longestValid("(((")); // 0
System.out.println("All close: " + longestValid("))")); // 0
System.out.println("Full: " + longestValid("(())()")); // 6
System.out.println("Adjacent: " + longestValid("()()")); // 4
}
}
Empty: 0
All open: 0
All close: 0
Full: 6
Adjacent: 4
What is the constant-space alternative?
The two-pass counter method uses no stack. Scan left to right counting opens and closes. Whenever they are equal, record the length. Whenever closes exceed opens, reset both to zero. Then scan right to left with the same logic but resetting when opens exceed closes. The maximum across both scans is the answer. This uses O(1) space.
package com.bank.service;
public class LVPConstantSpace {
public static int longestValid(String s) {
int open = 0, close = 0, max = 0;
// Left to right
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') open++; else close++;
if (open == close) max = Math.max(max, 2 * close);
else if (close > open) { open = 0; close = 0; }
}
open = 0; close = 0;
// Right to left
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') open++; else close++;
if (open == close) max = Math.max(max, 2 * open);
else if (open > close) { open = 0; close = 0; }
}
return max;
}
public static void main(String[] args) {
System.out.println(longestValid(")()())")); // 4
System.out.println(longestValid("(()")); // 2
}
}
4
2
How is this applied in banking systems?
At the National Bank of India, partially corrupted fee-formula fragments arrive from legacy systems. The formulas use round brackets for grouping, and corruption can break brackets at arbitrary positions. Instead of discarding the entire formula, the system finds the longest intact balanced section for salvage parsing, so the maximum usable portion of the formula is recovered.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class FormulaSalvage {
public static int longestBalancedSection(String formula) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
int max = 0;
for (int i = 0; i < formula.length(); i++) {
char c = formula.charAt(i);
if (c == '(') {
stack.push(i);
} else if (c == ')') {
stack.pop();
if (stack.isEmpty()) stack.push(i);
else max = Math.max(max, i - stack.peek());
}
}
return max;
}
public static void main(String[] args) {
String corrupt = ")((base+tax)*(rate+fee)))(extra";
int salvageable = longestBalancedSection(corrupt);
System.out.println("Formula: " + corrupt);
System.out.println("Longest balanced section length: " + salvageable);
}
}
Formula: )((base+tax)*(rate+fee)))(extra
Longest balanced section length: 23
What should a senior engineer know?
The index stack solution, the two-pass counter solution, and a dynamic programming formulation all solve this in O(n) time. The stack version is the most intuitive for interviews. The DP version defines dp[i] as the length of the longest valid substring ending at index i, using the relationship between matched pairs to fill the array. A senior engineer should know all three approaches and their space trade-offs: O(n) for stack, O(1) for two-pass counters, and O(n) for DP.
package com.bank.service;
public class LVPDynamicProgramming {
public static int longestValid(String s) {
int[] dp = new int[s.length()];
int max = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (dp[i - 1] > 0) {
int matchIdx = i - dp[i - 1] - 1;
if (matchIdx >= 0 && s.charAt(matchIdx) == '(') {
dp[i] = dp[i - 1] + 2 + (matchIdx >= 1 ? dp[matchIdx - 1] : 0);
}
}
max = Math.max(max, dp[i]);
}
}
return max;
}
public static void main(String[] args) {
System.out.println(longestValid(")()())")); // 4
System.out.println(longestValid("()(()")); // 2
}
}
4
2
Visual Overview
Index Stack Walk for ")()())"
─────────────────────────────
Init: stack = [-1]
i=0 ')': pop -1 → stack empty → push 0 as new base
stack = [0]
i=1 '(': push 1
stack = [1, 0]
i=2 ')': pop 1 → stack = [0] → len = 2 - 0 = 2, max=2
i=3 '(': push 3
stack = [3, 0]
i=4 ')': pop 3 → stack = [0] → len = 4 - 0 = 4, max=4
i=5 ')': pop 0 → stack empty → push 5 as new base
stack = [5]
Answer: 4
Base Marker Concept
────────────────────
String: ) ( ) ( ) )
Index: 0 1 2 3 4 5
▲ ▲
│ │
base 1 base 2
(unmatched ')') (unmatched ')')
Valid run "()()" spans indices 1..4
Length = 4 - base1_index = 4 - 0 = 4
Key Takeaway
Longest Valid Parentheses finds the length of the longest contiguous balanced substring, and unlike a simple validity check it needs positions, so I use a stack of indices seeded with a -1 base marker. For every ( I push its index. For every ) I pop, then if the stack is empty this closer is unmatched and becomes a new base that I push, otherwise the valid run length is the current index minus the new stack top, which I use to update the maximum.
The base marker is the heart of the method. The bottom of the stack always holds the index of the most recent position that broke validity, either the initial -1 or an unmatched closing bracket. Subtracting it from the current index captures the full length of the valid substring ending here, including runs that span several adjacent or nested pairs. That is why the stack stores indices rather than bracket characters.
The subtle correctness point is that I must pop before measuring. When I meet a closer, popping removes the matched opener's index and the new top becomes the boundary of the enclosing valid run, so the subtraction spans every inner completed pair. Measuring before popping would produce an off-by-one error, which is a classic bug in this problem. I also know the constant-space two-pass counter variant, scanning left to right and right to left and resetting when one count exceeds the other, which I offer when memory is tight.
In my banking project at the National Bank of India, I used this on grouping-marker strings from partially corrupted fee-formula fragments to recover the longest intact balanced section for salvage parsing. The base marker resets correctly at each broken section, so the system finds the maximum usable portion of the formula rather than discarding the entire string.
Remember one sentence: seed the index stack with -1, pop before measuring, and the valid run length is always the current index minus the new stack top.
---