InternDoor

Longest balanced bracket run

Hardstrings · stack · dynamic programming

Reported in interviews at (where)

You are given a string s made only of ( and ). A run of it is balanced when every ( in the run is closed by a later ) in the run, and no ) closes something that was never opened.

Return the length of the longest balanced run (characters next to each other). If there is none, return 0.

Example 1
Input
s = "())(())"
Output
4

"(())" at the end is balanced; the first "()" is only 2 long.

Example 2
Input
s = "(()"
Output
2

Only the last two characters close each other.

Example 3
Input
s = ")("
Output
0

Nothing here closes anything.

Limits

  • 0 <= s.length <= 100000
  • s[i] is ( or ).

Hints

Hint 1

A stack of positions works: keep the position just before the current balanced run at the bottom.

Hint 2

Or scan left to right counting opens and closes, then right to left.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.