Longest Prefix with Equal Counts
MediumPractice library · +20 XPstackhash mapprefix sum
Given a sequence of characters, where each character is either '(' or ')', find the length of the longest prefix of the sequence that contains an equal number of opening and closing parentheses. If no such non-empty prefix exists, output 0.
Input
A single line containing a string of '(' and ')' characters.
Output
A single integer representing the length of the longest prefix with equal counts of '(' and ')'.
Constraints
The input string contains between 1 and 200000 characters, inclusive.
Time limit 1 s (native code; slower languages get more)Memory 256 MB16 hidden tests
Example 1
Input
(()())
Output
6
The entire string has 3 '(' and 3 ')', so the length is 6.
Example 2
Input
())((
Output
4
Prefix '()' has length 2, with 1 '(' and 1 ')'. No longer prefix has equal counts.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
(()())
Example 2 input
())((