Definition
- Longest Valid Parentheses – find the length of the longest contiguous well-formed parentheses substring.
- Stack approach – seed a stack with -1; push indices of
(; on)pop, if stack empty push current index as new base, else length = current - stack top. - Sentinel -1 – lets the first valid run be measured without special casing since run length = index - (-1).
- Two-pass alternative – scan left-to-right counting opens and closes, record when equal, reset when closes exceed opens; repeat right-to-left.
- Complexity – O(n) time, O(n) space for stack or O(1) for two-pass.
A message-framing checker at National Bank of India finds the longest stretch of a protocol string where every open marker is properly closed. Rajesh remembers the position just before each unmatched point and measures balanced runs from there.
Understanding the Concepts
What is the Longest Valid Parentheses problem?
Given a string containing only ( and ), find the length of the longest contiguous substring that forms a valid parentheses sequence. For example, in "(()" the longest valid substring is "()" with length 2. In ")()())" the longest is "()()" with length 4.
package com.bank.core;
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); // sentinel
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
} else {
maxLen = Math.max(maxLen, i - stack.peek());
}
}
}
return maxLen;
}
public static void main(String[] args) {
System.out.println(longestValid("(()")); // 2
System.out.println(longestValid(")()())")); // 4
System.out.println(longestValid("")); // 0
}
}
2
4
0
How does the stack-of-indices approach work?
The stack holds indices, not characters. You seed it with -1 as a sentinel representing the position just before a valid run. For each (, push its index. For each ), pop the top.
After popping, if the stack is empty, this ) has no match, so push its index as a new base. If the stack is not empty, the new top is the position just before the current valid run, so the valid length is i - stack.peek(). Track the maximum.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class StackTraceDemo {
public static void main(String[] args) {
String s = ")()())";
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
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);
System.out.println("i=" + i + ": new base");
} else {
int len = i - stack.peek();
maxLen = Math.max(maxLen, len);
System.out.println("i=" + i + ": valid len=" + len + ", max=" + maxLen);
}
}
}
System.out.println("Longest: " + maxLen);
}
}
i=0: new base
i=2: valid len=2, max=2
i=4: valid len=4, max=4
i=5: new base
Longest: 4
Why is the sentinel -1 important?
The sentinel lets the very first valid run be measured without special casing. A run ending at index i that started at the beginning has length i - (-1) = i + 1. Without the sentinel, you would need extra logic to handle runs starting at index 0.
What is the constant-space two-pass alternative?
Scan left to right, counting opens and closes. When they are equal, record the current length (2 * opens). When closes exceed opens, reset both to zero. Then do the same scan right to left (resetting when opens exceed closes). Take the maximum from both scans.
The first scan misses valid sequences where opens always exceed closes (like "(()" never balances going left to right). The reverse scan catches those. Together they cover all cases.
package com.bank.core;
public class TwoPassSolution {
public static int longestValid(String s) {
int maxLen = 0, open = 0, close = 0;
// Left to right
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') open++; else close++;
if (open == close) maxLen = Math.max(maxLen, 2 * open);
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) maxLen = Math.max(maxLen, 2 * open);
else if (open > close) { open = 0; close = 0; }
}
return maxLen;
}
public static void main(String[] args) {
System.out.println(longestValid("(()")); // 2
System.out.println(longestValid(")()())")); // 4
}
}
2
4
What is the DP approach?
A 1D DP where dp[i] is the length of the longest valid parentheses ending at index i. If s[i] is (, dp[i] is 0 (a valid sequence cannot end with an open). If s[i] is ) and s[i-1] is (, then dp[i] = dp[i-2] + 2. If s[i] is ) and s[i-1] is ), check the character just before the valid sequence ending at i-1.
package com.bank.core;
public class DPApproach {
public static int longestValid(String s) {
int n = s.length();
int[] dp = new int[n];
int maxLen = 0;
for (int i = 1; i < n; i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
}
maxLen = Math.max(maxLen, dp[i]);
}
}
return maxLen;
}
public static void main(String[] args) {
System.out.println(longestValid("()(()")); // 2
System.out.println(longestValid("()(())")); // 6
}
}
2
6
What are the edge cases?
Edge cases include empty strings, all open, all close, single characters, and strings where the entire string is valid.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class ValidParensEdgeCases {
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 valid: " + longestValid("()()")); // 4
}
}
Empty: 0
All open: 0
All close: 0
Full valid: 4
What is the banking use case?
At National Bank of India, Pankaj's protocol parser finds the longest well-framed stretch of a message where every open marker has a matching close, to isolate the largest intact segment after corruption. The stack-based approach identifies the longest contiguous valid portion, and the two-pass counting alternative is used on memory-constrained infrastructure.
How do the three approaches compare?
| Approach | Time | Space | Clarity |
|---|---|---|---|
| Stack of indices | O(n) | O(n) | Most intuitive |
| Two-pass counting | O(n) | O(1) | Best space |
| DP array | O(n) | O(n) | Most complex |
Visual Overview
Longest Valid Parentheses: Stack Approach
═════════════════════════════════════════
Input: ")()())"
Stack: [-1] (sentinel)
i=0 ')': pop -1, stack empty → push 0
Stack: [0]
i=1 '(': push 1
Stack: [0, 1]
i=2 ')': pop 1, top=0 → len = 2-0 = 2, max=2
Stack: [0]
i=3 '(': push 3
Stack: [0, 3]
i=4 ')': pop 3, top=0 → len = 4-0 = 4, max=4
Stack: [0]
i=5 ')': pop 0, stack empty → push 5
Stack: [5]
Answer: 4
Key Takeaway
Longest Valid Parentheses asks for the longest contiguous well-formed substring, and the preferred solution uses a stack of indices seeded with a sentinel of -1. The sentinel represents the position just before a valid run. For each ( push its index. For each ) pop the top: if the stack is empty, push the current index as a new base; otherwise the valid length is current minus the new top.
The sentinel is the elegance: it lets a valid run starting at the very beginning be measured as i - (-1) without special casing. The stack approach runs in O(n) time and O(n) space. The two-pass counting alternative achieves O(1) space by scanning left-to-right and right-to-left, recording balanced lengths and resetting when one type exceeds the other.
In the banking project at National Bank of India, Pankaj's protocol parser uses this to find the longest intact framed segment after message corruption. The stack approach is used in normal services, and the two-pass alternative runs on memory-constrained infrastructure.
Remember one sentence: seed a stack with -1, push open indices, pop on close, and measure valid lengths as current index minus the new stack top.
---