Equal Point in Brackets

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.

Splitting at position 0 means the left side is empty.
Splitting at position n means the right side is empty.

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:

The number of closing brackets from index 4 to the end is also:

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:

The number of opening brackets encountered so far (open).
The number of closing brackets remaining in the suffix (close).

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:

open represents the number of opening brackets to the left of the split.
close represents the number of closing brackets to the right of the split.

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:

Hence, the answer is:

Complexity Analysis

Time Complexity

O(n)

One traversal to count closing brackets.
One traversal to find the equal point.

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.