Problem Statement
The Equal Point in Brackets problem asks us to find a position in a string containing only opening brackets '(' and closing brackets ')' such that the number of opening brackets before that position is equal to the number of closing brackets from that position to the end of the string.
A split can occur at any position from 0 to n, where n is the length of the string.
Understanding the Problem
Consider the string:
(())))(
If we split the string at index 4, the left part is:
(())
and the right part is:
))(
The number of opening brackets before index 4 is:
2
The number of closing brackets from index 4 to the end is also:
2
Therefore, index 4 is an equal point.
Brute Force Approach
A straightforward approach would be to check every possible split position and count brackets on both sides.
For each position:
Count the opening brackets on the left side.
Count the closing brackets on the right side.
Compare the two counts.
However, this would require repeatedly scanning the string, resulting in a time complexity of:
O(n²)
which is inefficient for large inputs.
Efficient Approach
A better approach is to observe that we only need two running counts:
Step 1: Count All Closing Brackets
Traverse the string once and count all closing brackets.
Store this count in:
close
Step 2: Traverse the String
While traversing the string from left to right:
Before processing the current character, check whether:
open == close
If they are equal, the current position is the first valid equal point.
If the current character is '(', increment:
open
If the current character is ')', decrement:
close
because that bracket is no longer part of the remaining suffix.
Why This Works
At every position:
When:
open == close
the current position satisfies the required condition and is an equal point.
Since we process each character only once after the initial counting phase, the solution remains highly efficient.
Algorithm
Count all closing brackets in the string and store the result in close.
Initialize open = 0.
Traverse the string from left to right.
Before processing each character, check if open == close.
If true, return the current index.
Update open or close based on the current character.
If no equal point is found during traversal, return s.length().
Java Implementation
class Solution {
public int findIndex(String s) {
int close = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ')') {
close++;
}
}
int open = 0;
for (int i = 0; i < s.length(); i++) {
if (open == close) {
return i;
}
if (s.charAt(i) == '(') {
open++;
} else {
close--;
}
}
return s.length();
}
}
Example Walkthrough
Input
(())))(
Initial Count
Number of closing brackets:
close = 4
Number of opening brackets encountered so far:
open = 0
Traversal
| Index | Character | Open | Close | Equal? |
|---|
| 0 | ( | 0 | 4 | No |
| 1 | ( | 1 | 4 | No |
| 2 | ) | 2 | 4 | No |
| 3 | ) | 2 | 3 | No |
| 4 | ) | 2 | 2 | Yes |
The first position where:
open == close
is:
4
Hence, the answer is:
4
Complexity Analysis
Time Complexity
O(n)
Each character is processed at most twice.
Space Complexity
O(1)
No extra data structures are used.
Key Insight
Instead of recomputing bracket counts for every possible split position, maintain two running counts: the number of opening brackets seen so far and the number of closing brackets remaining in the suffix. The first position where these counts become equal is the required equal point. This transforms an O(n²) solution into an optimal O(n) solution with constant extra space.
Summary
The Equal Point in Brackets problem can be solved efficiently by tracking the number of opening brackets encountered so far and the number of closing brackets remaining ahead. By first counting all closing brackets and then updating the counts during a single traversal, we can identify the first valid split position in linear time while using only constant extra space.