MismatchedStrings | Topcoder Archive

Problem Statement

Well-parenthesized strings are defined using the following rules:

The empty string is well-parenthesized.
If S is a well-parenthesized string, then (S) is a well-parenthesized string.
If S and T are well-parenthesized strings, then ST is a well-parenthesized string.
Every well-parenthesized string can be created using the previous rules only.

In this problem we will deal with the complement of this set of strings: The strings that consist only of the characters '(' and ')', but are not well-parenthesized. We will call these strings mismatched.

You are given an int N and a long K. All mismatched strings of length N can be ordered lexicographically, and numbered sequentially, starting with zero. Return the string that will get the number K in this order. If there is no such string, return the empty string instead.

Definition

Class:: MismatchedStrings
Method:: getString
Parameters:: int, long
Returns:: String
Method signature:: String getString(int N, long K)
(be sure your method is public)

Notes

Given two different strings S and T of equal length, S is lexicographically smaller than T if it has a smaller character at the first position where they differ.
The ASCII value of '(' is less than the ASCII value of ')'.

Constraints

N will be between 1 and 50, inclusive.
K will be between 0 and 2^N - 1, inclusive.

Examples

```
4
```
```
0
```
```
Returns: "(((("
```
For any length, the lexicographically smallest mismatched string consists of '(' characters only.
```
4
```
```
4
```
```
Returns: "())("
```
There are 14 mismatched strings of length 4. The first five are "((((", "((()", "(()(", "()((", and "())(". Note that we use a 0-based index, hence K=4 corresponds to the fifth mismatched string.
```
6
```
```
63
```
```
Returns: ""
```
There are less than 64 mismatched strings of length 6.
```
7
```
```
13
```
```
Returns: "((())()"
```

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.