Bracket107
SRM 670 · 2015-08-31 · by subscriber
Problem Statement
Correct bracket sequences are strings in which each character is a '(' or a ')', the total number of opening brackets is the same as the total number of closing brackets, and each prefix contains at least as many opening as closing brackets. For example, the shortest few correct bracket sequences are "", "()", "(())", and "()()".
The subsequence of a string S is any string that can be obtained by erasing zero or more characters of S. For example, each of the strings "", "ace", and "abcde" is a subsequence of "abcde".
We will use LCS(S,T) to denote the length of a longest common subsequence of strings S and T. In other words, LCS(S,T) is the largest k such that there is a string U of length k that is both a subsequence of S and a subsequence of T. For example, LCS("abcde","bad") = 2.
You are given a
- t will have the same length as s,
- t will be a correct bracket sequence,
- t will not be equal to s,
- LCS(s,t) will be as large as possible.
Notes
- You may assume that the answer for each valid test case fits into a signed 32-bit integer variable.
Constraints
- s will contain between 4 and 50 characters, inclusive.
- Each character in s will be either '(' or ')'.
- s will be a correct bracket sequence.
"(())" Returns: 1
There is only one other correct bracket sequence of the same length.
"(())()" Returns: 3
There are four other correct bracket sequences of the same length: "((()))", "()(())", "()()()", and "(()())". However, only in three of those four cases the length of the longest common subsequence is 5. LCS( "(())()", "()(())" ) is only 4, therefore "()(())" is not a valid choice of the string t.
"()()()" Returns: 3
"(((())))" Returns: 5
"((())())" Returns: 9
Submissions are judged against all 111 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Bracket107 with a public method int yetanother(string s) · 111 test cases · 2 s / 256 MB per case