Connection Status:
Competition Arena > RemovingParenthesis

RemovingParenthesis

SRM 714 · 2017-02-20 · by lg5293

SRM 714 · 2017-02-20 · by lg5293 · Brute Force, Recursion
Class Name: RemovingParenthesis
Return Type: int
Method Name: countWays
Arg Types: (string)
Problem Statement

Problem Statement

Correct parentheses sequences can be defined recursively as follows:

  • The empty string "" is a correct sequence.
  • If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
  • If "X" is a correct sequence, then "(X)" is a correct sequence.
  • Each correct parentheses sequence can be derived using the above rules.

Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".

You are given a String s that is guaranteed to be a correct parentheses sequence. A removal is an action that consists of two steps:

  1. Remove the first opening parenthesis in s.
  2. Remove one closing parenthesis in s. After you do so, s must again be a correct parentheses sequence.

Compute and return the number of distinct ways in which s can be reduced to an empty string by performing consecutive removals. Two ways are considered distinct if there is a step in which you remove a different closing parenthesis. (See Example 1 for clarification.) It is guaranteed that the correct return value will always fit into a 32-bit signed integer.

Constraints

  • s will have between 2 and 20 characters, inclusive.
  • s will be a correct parentheses sequence.
Examples
0)
"()()()()()"
Returns: 1

In each removal we have to choose the leftmost closing parenthesis.

1)
"(((())))"
Returns: 24

In each removal we can choose any closing parenthesis we want. Note that these count as distint choices, even though all choices lead to the same string. Thus, there are 4*3*2*1 = 24 different sequences of removals that change s into an empty string.

2)
"((()()()))"
Returns: 54

Below is one of the 54 possible sequences of removals. Remember that in each step we also remove the first opening parenthesis. Remove the fourth closing parenthesis: "(()()())" Remove the second closing parenthesis: "()(())" Remove the first closing parenthesis: "(())" Remove the second closing parenthesis: "()" Remove the first closing parenthesis: ""

3)
"(())(())(())"
Returns: 8
4)
"((()))(()(()))((()))"
Returns: 432

Submissions are judged against all 51 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RemovingParenthesis with a public method int countWays(string s) · 51 test cases · 2 s / 256 MB per case

Submitting as anonymous