JustBrackets
SRM 731 · 2018-03-16 · by subscriber
SRM 731 · 2018-03-16 · by subscriber · Dynamic Programming
Problem Statement
Problem Statement
Hero has a String s that is guaranteed to be a correct bracket sequence (see Notes for a definition).
Hero can perform the following operation: he can choose a substring of the form "()" and erase it.
For example, he can change "(())()" into either "()()" or "(())" by erasing either the first or the second occurrence of the substring "()".
Find and return the lexicographically smallest non-empty string Hero can produce from s by performing the operation zero or more times.
Notes
- Given two distinct strings A and B, we say that A is lexicographically smaller than B if either A is a prefix of B, or there is a nonnegative integer x such that the first x characters of A match the first x characters of B, and the next character of A is smaller than the next character of B.
- Correct bracket sequences include the empty string and everything that can be derived using the following rule: if S and T are correct bracket sequences then both (S) and ST are also correct bracket sequences.
Constraints
- s will contain between 2 and 100 characters, inclusive.
- Each character in s will be either '(' or ')'.
- s will be a correct bracket sequence.
Examples
0)
"()" Returns: "()"
As we are looking for a non-empty string, Hero cannot erase the last pair of brackets.
1)
"()()" Returns: "()"
2)
"(())" Returns: "(())"
Even though Hero could erase one pair of brackets, it is better not to do so: the string "(())" is lexicographically smaller than the string "()".
3)
"(()(()))" Returns: "((()))"
4)
"((())()(()(())(())))" Returns: "(((())(())))"
Submissions are judged against all 95 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class JustBrackets with a public method string getSmallest(string s) · 95 test cases · 2 s / 256 MB per case