Statistics

Problem Statement for "InterleavingParenthesisDiv2"

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 two Strings s1 and s2. Each character in these strings is a parenthesis, but the strings themselves are not necessarily correct sequences of parentheses.

You would like to interleave the two sequences so that they will form a correct parentheses sequence. Note that sometimes two different ways of interleaving the two sequences will produce the same final sequence of characters. Even if that happens, we count each of the ways separately. (See Example 0 for a clarification.)

Compute and return the number of different ways to produce a correct parentheses sequence, modulo 10^9 + 7.

Definition

Class:
InterleavingParenthesisDiv2
Method:
countWays
Parameters:
String, String
Returns:
int
Method signature:
int countWays(String s1, String s2)
(be sure your method is public)

Constraints

  • s1, s2 will each have between 1 and 50 characters, inclusive.
  • Each character of s1, s2 will be either '(' or ')'.

Examples

  1. "(()"

    "())"

    Returns: 19

    The 19 ways are: Here, the red characters come from the first sequence, and the blue characters come from the second sequence.

  2. ")"

    "("

    Returns: 1

  3. "((((("

    ")))))"

    Returns: 42

  4. "()(()"

    "))((())"

    Returns: 10

  5. "()()()()()()()()()()()()()()()"

    "()()()()()()()()"

    Returns: 493841617

    Don't forget about the mod.

  6. "())())))"

    "))(((("

    Returns: 0

  7. "))()(((())))))()))"

    "((()(()(())(((()"

    Returns: 488433476

  8. "((((((((((((((((())("

    "((()))(()))))(((()())()))(()))((()))))))))))))))"

    Returns: 829753739

  9. "()()(((((((()))"

    ")(((((((((())))))))))))))"

    Returns: 115196654

  10. "()("

    "(())(()(()()))())"

    Returns: 969

  11. "((((()()"

    ")())((()))))"

    Returns: 43887

  12. "))))))()(((((((((()((()))))(()(()()(((()"

    "()()))()((())())))))(()()()))(())))))())))(((((((("

    Returns: 0

  13. "))))(())(()(((())))))()((())()()())((((((()))()("

    "()))))))(()()())))))(())(()(()((((()))((()(())(((("

    Returns: 0

  14. "()((((((((((((())((((())))"

    "()))()(()))))()()(()))))))))"

    Returns: 944954230

  15. ")((((((((()(((()(()))))))))))))))))"

    "()((((())(((((((())))))"

    Returns: 379054699

  16. "()((()()))(()((()()(((((((())(())(((()))))))))))))"

    "((()()()())))))((((())(()(((()((()(())))))))"

    Returns: 479014504

  17. "(((((((("

    "((((((((()()))((((((((((()))))))))))))))))))))))))"

    Returns: 616123216

  18. "()((((((((()(((()(((((((()((((((())))))))))"

    "(()(()(())()(())(())()))()()())(())))))))))))))))"

    Returns: 8749767

  19. "((((())(()()(()))()((()"

    "(((((())((()((((((())((()((()))))))))))))))))))))"

    Returns: 458288826

  20. "(((((((()()(((((()()((((((((((()))))))))))))))))))"

    "()((()(((()((((()(()((((()))()()))))))))))))))))"

    Returns: 501921695

  21. "(((())()))))))()))((()())(((((())"

    "(((()((((()()((()()(()((())()(()()())))))))))))"

    Returns: 817005311

  22. ")(()))(((((((((()(((((((()()((((("

    "))())()))()()((())))()())())())()))))))))))"

    Returns: 0

  23. "(((((((((((((((((((((()())))"

    "))))()))())))))))))()(()))))"

    Returns: 56479236

  24. ")))(("

    "))))()((()((((((((((())))))))"

    Returns: 0

  25. "("

    ")))()()()()((()))(())((())())()()(()()((())"

    Returns: 0

  26. ")(((()()())()())(()))))((()()(()))(()))((((((((("

    "())))(())())())()))(()))(())()(())()(()(()"

    Returns: 0

  27. "((()(((()(()(()(((()()))()))))))))))"

    "((()(((((()((()((((()(((()))))))))))))))"

    Returns: 918919795

  28. "())((()()(((())())((((((())))()(()))(()((("

    "()()())()))())))))()))()))()))))()(()()((((((("

    Returns: 0

  29. ")))()(())))))))()())))()()))))()()))))"

    "(()(((((((()()((())))))(((()(((((()()((()((((("

    Returns: 898557502

  30. "(())())())(()()))())()())))((()())))))))))"

    ")(((((((((((()(()((((((((()())()))))"

    Returns: 115256033

  31. "()((((()(((((((((((((((((((((())))"

    "()(()(()))())()))(()(())()()))))))))))))))))))))"

    Returns: 914068968

  32. "(((((()()((()(((((((()(())))))))))))))"

    "((()(()((((((((()((((()())))))))))))))))))"

    Returns: 252107905

  33. "(()())))(()((()()())((()()))(((()()()((()(())))"

    ")()))))((()"

    Returns: 0

  34. "(()()(((((((())))))(())()))(((()))))))))))))"

    "()))((((((()(((((()(()())((())()))"

    Returns: 990373168

  35. "(()()))())())()(())()((((((()))))))))))))))))"

    "(((((((()()(((()()(()((((()()))"

    Returns: 244147384

  36. "))(((()(()((())((((((((()(()(()))((((()())))))))"

    ")(((()(()))))()()))))))(()()))"

    Returns: 0

  37. ")((((())(((((((((((()((()))()))))))))))))))))"

    "(((((((((()((((((()(())(((())))))))))))))))"

    Returns: 517153446

  38. ")())(((((((()(()((()((()()((()()())))))))))))"

    "()((()(((((()()(())(((()()()(((()()))))))))))))))"

    Returns: 774373786

  39. "(()(((()(((()(()()()((((()()()))))))))))))))))"

    "((((((()(()((((())(((()()()(()))))))))))"

    Returns: 762151133

  40. ")((())((((((((()((((((())(((((()))))))))))))))"

    "()())((((((()))(()()))()(((()())))))))))"

    Returns: 121753436

  41. "(())))))(()))))()()()())(((((("

    "(())(()(((())()())"

    Returns: 0

  42. "(())((((((((((((())()(((())))))))))))))))))))))))"

    "((((()(()()(()((((((()((())))))"

    Returns: 781593559

  43. ")()())()((((((((((((()("

    "(())())))((((()((())()(((()))))))))))))))))"

    Returns: 950522342

  44. "((((()()(((()((((((()(((()(())()((())))))))))))"

    "))()))))(()())())()"

    Returns: 963382565

  45. "((()(((()()(((())()))())((()))()())())"

    "()((())()()())())()((()())(())))))(()()("

    Returns: 607946813

  46. "()))))()))()())(((()())((()()))()(())())))))))"

    "((((()(((((((())()(((()(((((()((())))((())))))))"

    Returns: 756504935

  47. "(((((((()(((())))()(()((())(())))))()())()))))"

    "((((((()(())()()))))))"

    Returns: 137543397

  48. "))((((((()((()())((((((((()()(((()(()(()(()"

    "(()))))(((((()))))())))())()((()))))())))))))))))"

    Returns: 314887681

  49. ")))(()(((((((())((((()(()()()((()()("

    "))()))(()((()())()(((()))))))(((((()))))))))))))"

    Returns: 0

  50. "(((((((()(())((()(()(((((((()())((((()))))))))"

    "(())()(()()))())()(()(()))(())(()())))))))))))"

    Returns: 136110323

  51. "()))((()(((()()(()()())())((()((()(((((("

    "))())())(((()()))()))(())))()(((()()()())())))))))"

    Returns: 0

  52. "((((()(()(()((((((((((((()))))))))"

    "()((((((()(()((((())((((()))))))))))))))))))))))))"

    Returns: 404253529

  53. "(((((((()(((()))))))))))))"

    "(((((()((((((())))))))))"

    Returns: 659185414

  54. "(((()(((((()()(()(((((((()))))))"

    "((((((()((((()()(())((()))))))))))))))))))))))"

    Returns: 143223394

  55. "(((()((()(()()((((((((((()(()((())))))))))))))"

    ")))))())(((())((())()()(()()(((())))))))"

    Returns: 291764122

  56. "(((()(((())(((((((((((((((()))))))))))))))))))"

    "())((((((((((((((((((((((())))))))))))))))))))))))"

    Returns: 14554223

  57. ")((()))((()))())))()((()))))((((((((((((("

    "()((("

    Returns: 0

  58. "(()))()))()))())(((()))))))()()))))(((("

    "(()(())))))())()(((((()()))()(((((((((((((((((((("

    Returns: 0

  59. ")()()((())((()((()(((("

    "()((())()("

    Returns: 0

  60. ")()(((((()(()(((()()(((((((()()())))))))"

    "(()("

    Returns: 0

  61. "(((()(((()((()(()())((()()((((()(()()()(())(((((("

    "))()())))))))(((()(())))))())(()())()()"

    Returns: 0

  62. "(((()())()())(()"

    "()()((()()))((())()()()))(())()()((((((((("

    Returns: 0

  63. ")(()()())(()(((((()(((((((("

    "))()())(()(()()))"

    Returns: 0

  64. "((()()((((()(((((())))"

    "((((()(()()))((())))"

    Returns: 0

  65. "())))("

    "()((((((()(((((((())"

    Returns: 0

  66. "((()((()(((("

    "))((())((("

    Returns: 0

  67. "("

    "("

    Returns: 0

  68. "((((("

    ")"

    Returns: 0

  69. "())))))))))))"

    "(((((((((((((((((())())"

    Returns: 0

  70. "()()()()()()()()()()()()()()()()()()()()"

    "()()()()()()()()()()()()()()()()()()()()"

    Returns: 720596125

  71. "(((((((((((((((((((((((((((((((((((((((((((((((((("

    "(((((((((((((((((((((((((((((((((((((((((((((((((("

    Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: