RepeatingFreeStrings | Topcoder Archive

Problem Statement

A binary string s is called "repeating free" if no proper prefix equals a proper suffix of the same lengh. A substring is called "proper" if it differs from the whole string. For example, strings "0101011", "10", "10111100" are repeating free, but the string "01101011" is not.

Return the k-th string among all repeating free strings with length n in lexicographical order (k is a 0-based index). Return an empty string if it doesn't exist.

Definition

Class:: RepeatingFreeStrings
Method:: kthString
Parameters:: int, int
Returns:: String
Method signature:: String kthString(int n, int k)
(be sure your method is public)

Constraints

n will be between 1 and 50, inclusive.
k will be between 0 and 2000000000, inclusive.

Examples

```
2
```
```
0
```
```
Returns: "01"
```
All repeating free strings of length 2 are "01" and "10".
```
2
```
```
1
```
```
Returns: "10"
```
```
3
```
```
2
```
```
Returns: "100"
```
All repeating strings of length 3 are "001", "011", "100", "110".
```
5
```
```
2
```
```
Returns: "00101"
```

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.