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"
10
75
Returns: "0010110011"
15
5000
Returns: "101010001011100"
20
102404
Returns: "01000011010110010111"
25
89438
Returns: "0000000101011111001010111"
18
1000000000
Returns: ""
1
0
Returns: "0"
2
0
Returns: "01"
3
3
Returns: "110"
4
3
Returns: "1000"
5
4
Returns: "01011"
6
11
Returns: "101000"
7
4
Returns: "0001001"
8
12
Returns: "00011011"
9
47
Returns: "001110101"
10
9
Returns: "0000010011"
11
247
Returns: "01010111111"
12
591
Returns: "100110110000"
13
1854
Returns: "1110011000100"
14
4240
Returns: "11111010001010"
15
2196
Returns: "001010000010101"
16
732
Returns: "0000010111010111"
17
7883
Returns: "00100011100011101"
18
16010
Returns: "001001000100011111"
19
95931
Returns: "1100100010110101000"
20
88209
Returns: "00110110010001001111"
21
462365
Returns: "111001001100100100010"
22
321551
Returns: "0011000000001010101101"
23
511032
Returns: "00100100001111001000011"
24
4172883
Returns: "111101011100110101101100"
25
1857833
Returns: "0010000001101110011101111"
26
11182940
Returns: "10111000111001011100101100"
27
27150413
Returns: "110110001000101010111101010"
28
51419304
Returns: "1101000001000100101101101010"
29
82199165
Returns: "10101010100110001101110110000"
30
77023615
Returns: "001011000010000111101000011011"
31
364351319
Returns: "1011110000001111000111100000000"
32
240580643
Returns: "00100000111000011111001111110111"
33
1047812351
Returns: "010111011101011100110101010110011"
34
277579255
Returns: "0000100010001110110010111011110111"
35
2000000000
Returns: "00100010011000101011101110101001011"
36
2000000000
Returns: "000011111110001011000001000111011101"
37
2000000000
Returns: "0000011110101110010100100000011000101"
38
2000000000
Returns: "00000011110001111111011111100010110001"
39
2000000000
Returns: "000000011110000001011011011001101100001"
40
2000000000
Returns: "0000000011101111010010101100010110001011"
41
2000000000
Returns: "00000000011101110110110101000011010011111"
42
2000000000
Returns: "000000000011101110101000101011110101010011"
43
2000000000
Returns: "0000000000011101110100001101110100001110111"
44
2000000000
Returns: "00000000000011101110011110010000011010100101"
45
2000000000
Returns: "000000000000011101110011100100001010100010011"
46
2000000000
Returns: "0000000000000011101110011011101001111001110001"
47
2000000000
Returns: "00000000000000011101110011011001110001001000111"
48
2000000000
Returns: "000000000000000011101110011011000000010100100111"
49
2000000000
Returns: "0000000000000000011101110011010111001011000011101"
50
2000000000
Returns: "00000000000000000011101110011010110101111100010011"
1
2
Returns: ""
2
3
Returns: ""
3
6
Returns: ""
4
9
Returns: ""
5
13
Returns: ""
6
22
Returns: ""
7
44
Returns: ""
8
77
Returns: ""
9
156
Returns: ""
10
285
Returns: ""
11
574
Returns: ""
12
1125
Returns: ""
13
2244
Returns: ""
14
4428
Returns: ""
15
8855
Returns: ""
16
17637
Returns: ""
17
35260
Returns: ""
18
70342
Returns: ""
19
140691
Returns: ""
20
281093
Returns: ""
21
562168
Returns: ""
22
1123740
Returns: ""
23
2247488
Returns: ""
24
4493838
Returns: ""
25
8987661
Returns: ""
26
17973090
Returns: ""
27
35946176
Returns: ""
28
71887905
Returns: ""
29
143775810
Returns: ""
30
287542757
Returns: ""
31
575085480
Returns: ""
32
1150153337
Returns: ""
1
1
Returns: "1"
4
5
Returns: "1110"
7
39
Returns: "1111110"
11
567
Returns: "11111111110"
14
4423
Returns: "11111111111110"
16
17621
Returns: "1111111111111110"
20
281075
Returns: "11111111111111111110"
24
4493827
Returns: "111111111111111111111110"
28
71887895
Returns: "1111111111111111111111111110"
30
287542735
Returns: "111111111111111111111111111110"
31
575085471
Returns: "1111111111111111111111111111110"
1
2000000000
Returns: ""
2
2000000000
Returns: ""
5
2000000000
Returns: ""
13
2000000000
Returns: ""
1
2
Returns: ""
1
3
Returns: ""
1
4
Returns: ""
2
1
Returns: "10"
2
2
Returns: ""
2
3
Returns: ""
2
4
Returns: ""
2
5
Returns: ""
3
4
Returns: ""