Longest Balanced Bracket Substring
Solve this Problems consisting only of '(' and ')', find the length of the longest contiguous substring that is a balanced bracket sequenceBalancedEvery '(' in the substring has a matching ')' later within it, and every ')' has a matching '(' earlier within it — nothing left unmatched, anywhere in that stretch..
Checking every substring works but re-treads the same ground repeatedly. A single pass with a stack of indices (not characters) avoids that: keep a sentinel marking the last position that broke a run, push the index of every '(', and on every ')', pop the matching '(' off. Whatever's left on top afterward marks exactly where the current balanced run's boundary sits — so its length is simply the current index minus that value, read off directly with no re-scanning. If a ')' ever finds nothing to pop (the stack was already down to just the sentinel), it becomes the new sentinel itself, since no balanced run can reach back across an unmatched closing bracket.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ s.length ≤ 20 - ◆
s consists only of the characters '(' and ')'
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Check Every Substring
BruteTry every possible substring (every start i and every even-length end j), and for each one, scan it to check whether it's fully balanced — track a running open-bracket count, failing if it ever goes negative or doesn't return to exactly 0. Keep the length of the longest one that checks out. There are O(n²) substrings to try, and validating each one costs O(n), so this is O(n³) overall — thorough, but it repeats a lot of scanning that overlapping substrings share.
O(n³)O(n)1class Solution {
2 public int longestValidSubstring(String s) {
3 int best = 0;
4 int n = s.length();
5 for (int i = 0; i < n; i++) {
6 for (int j = i + 2; j <= n; j += 2) {
7 if (isValid(s.substring(i, j))) {
8 best = Math.max(best, j - i);
9 }
10 }
11 }
12 return best;
13 }
14
15 private boolean isValid(String sub) {
16 int open = 0;
17 for (char c : sub.toCharArray()) {
18 if (c == '(') open++;
19 else {
20 open--;
21 if (open < 0) return false;
22 }
23 }
24 return open == 0;
25 }
26}Optimal — Stack of Indices
OptimalKeep a stack of indices instead of characters, seeded with -1 as a sentinel marking "the position just before the current balanced run could start." Push the index of every '('. On ')', pop — that removes the '(' this character just matched. If the stack is now empty, this ')' had nothing to match at all, so it becomes the new sentinel (push its own index). Otherwise, what's left on top of the stack is the index just before the current balanced run's start, so the run's length is simply the current index minus that top value — update the best seen so far. One pass, one push or pop per character.
O(n)O(n)1class Solution {
2 public int longestValidSubstring(String s) {
3 Deque<Integer> stack = new ArrayDeque<>();
4 stack.push(-1);
5 int best = 0;
6 for (int i = 0; i < s.length(); i++) {
7 if (s.charAt(i) == '(') {
8 stack.push(i);
9 } else {
10 stack.pop();
11 if (stack.isEmpty()) {
12 stack.push(i);
13 } else {
14 best = Math.max(best, i - stack.peek());
15 }
16 }
17 }
18 return best;
19 }
20}