Problem Statement
The longest common subsequence (LCS) of two strings A and B is a string C that is a subsequence of each of them and has the largest length among all strings with this property. Let f(A,B) be the length of the LCS of strings A and B. For example, we have f("101", "111000") = 2, f("101", "110011") = 3, and f("00", "1111") = 0.
You are given three small positive integers ab, bc, and ca. Please find three strings A, B, C such that:
- Each of the strings contains only the characters '0' and '1'.
- The length of each string is between 1 and 1,000, inclusive.
- f(A, B) = ab
- f(B, C) = bc
- f(C, A) = ca
You may assume that a solution always exist. If there are multiple solutions you may return any of them.
Definition
- Class:
- ConstructLCS
- Method:
- construct
- Parameters:
- int, int, int
- Returns:
- String
- Method signature:
- String construct(int ab, int bc, int ca)
- (be sure your method is public)
Constraints
- ab will be between 1 and 50, inclusive.
- bc will be between 1 and 50, inclusive.
- ca will be between 1 and 50, inclusive.
Examples
3
4
2
Returns: "101 1010101 1111"
The returned string corresponds to the following solution: A = "1111" B = "101" C = "1010101" We can easily verify that the only LCS of A and B is "11", the only LCS of B and C is "101", and the only LCS of C and A is "1111".
7
4
4
Returns: "10101010 1010101 1011"
There are other solutions like: A = "1110000", B = "1110000", C = "0000".
8
7
8
Returns: "110101001011 010101101 10101010"
8
6
7
Returns: "110101010 10101010 1111010"
15
17
19
Returns: "000100101101111011000 11110111010011101010 100100001010101001010101000011111"
50
50
50
Returns: "11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111"
44
26
11
Returns: "00000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000111111111111111 00000000000111111111111111"
29
49
17
Returns: "00000000000000000111111111111 0000000000000000000000000000000000000000000000000111111111111 0000000000000000000000000000000000000000000000000"
39
45
43
Returns: "0000000000000000000000000000000000000001111 000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000001111"
39
2
5
Returns: "000000000000000000000000000000000000000111 000000000000000000000000000000000000000 00111"
37
13
27
Returns: "000000000000000000000000000000000000011111111111111 0000000000000000000000000000000000000 000000000000011111111111111"
20
43
8
Returns: "00000000111111111111 0000000000000000000000000000000000000000000111111111111 0000000000000000000000000000000000000000000"
3
49
5
Returns: "00011 0000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000011"
47
50
37
Returns: "00000000000000000000000000000000000001111111111 000000000000000000000000000000000000000000000000001111111111 00000000000000000000000000000000000000000000000000"
24
39
47
Returns: "00000000000000000000000000000000000000000000000 000000000000000000000000111111111111111 00000000000000000000000000000000000000000000000111111111111111"
43
48
44
Returns: "00000000000000000000000000000000000000000001 000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000001"
17
21
34
Returns: "0000000000000000000000000000000000 000000000000000001111 00000000000000000000000000000000001111"
17
50
8
Returns: "00000000111111111 00000000000000000000000000000000000000000000000000111111111 00000000000000000000000000000000000000000000000000"
32
8
16
Returns: "0000000000000000000000000000000011111111 00000000000000000000000000000000 0000000011111111"
33
1
36
Returns: "00000000000000000000000000000000000011111111111111111111111111111111 011111111111111111111111111111111 000000000000000000000000000000000000"
45
46
44
Returns: "000000000000000000000000000000000000000000001 00000000000000000000000000000000000000000000001 0000000000000000000000000000000000000000000000"
22
8
14
Returns: "0000000000000000000000111111 0000000000000000000000 00000000111111"
41
4
7
Returns: "00000000000000000000000000000000000000000111 00000000000000000000000000000000000000000 0000111"
26
50
22
Returns: "00000000000000000000001111 000000000000000000000000000000000000000000000000001111 00000000000000000000000000000000000000000000000000"
44
19
7
Returns: "00000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000111111111111 0000000111111111111"
27
8
34
Returns: "00000000000000000000000000000000001111111111111111111 000000001111111111111111111 0000000000000000000000000000000000"
33
23
6
Returns: "000000000000000000000000000000000 00000000000000000000000000000000011111111111111111 00000011111111111111111"
34
36
24
Returns: "0000000000000000000000001111111111 0000000000000000000000000000000000001111111111 000000000000000000000000000000000000"
12
41
13
Returns: "0000000000001 00000000000000000000000000000000000000000 000000000000000000000000000000000000000001"
37
30
1
Returns: "0000000000000000000000000000000000000 000000000000000000000000000000000000011111111111111111111111111111 011111111111111111111111111111"
50
42
39
Returns: "00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000111 000000000000000000000000000000000000000111"
44
19
8
Returns: "00000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000011111111111 0000000011111111111"
37
40
26
Returns: "0000000000000000000000000011111111111 000000000000000000000000000000000000000011111111111 0000000000000000000000000000000000000000"
18
48
14
Returns: "000000000000001111 0000000000000000000000000000000000000000000000001111 000000000000000000000000000000000000000000000000"
30
24
6
Returns: "000000000000000000000000000000 000000000000000000000000000000111111111111111111 000000111111111111111111"
41
22
41
Returns: "000000000000000000000000000000000000000001111111111111111111 00000000000000000000001111111111111111111 00000000000000000000000000000000000000000"
10
3
7
Returns: "00000000001111 0000000000 0001111"
35
9
14
Returns: "0000000000000000000000000000000000011111 00000000000000000000000000000000000 00000000011111"
13
28
10
Returns: "0000000000111 0000000000000000000000000000111 0000000000000000000000000000"
35
24
46
Returns: "000000000000000000000000000000000000000000000011111111111 00000000000000000000000011111111111 0000000000000000000000000000000000000000000000"
42
49
20
Returns: "000000000000000000001111111111111111111111 00000000000000000000000000000000000000000000000001111111111111111111111 0000000000000000000000000000000000000000000000000"
9
46
33
Returns: "000000000111111111111111111111111 0000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000111111111111111111111111"
15
47
47
Returns: "00000000000000000000000000000000000000000000000 00000000000000011111111111111111111111111111111 0000000000000000000000000000000000000000000000011111111111111111111111111111111"
4
48
46
Returns: "0000111111111111111111111111111111111111111111 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111"
39
23
21
Returns: "000000000000000000000000000000000000000 00000000000000000000000000000000000000011 00000000000000000000011"
26
1
23
Returns: "000000000000000000000000001111111111111111111111 00000000000000000000000000 01111111111111111111111"
19
50
33
Returns: "000000000000000000011111111111111 00000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000011111111111111"
1
41
43
Returns: "0000000000000000000000000000000000000000000 01111111111111111111111111111111111111111 00000000000000000000000000000000000000000001111111111111111111111111111111111111111"
22
5
9
Returns: "00000000000000000000001111 0000000000000000000000 000001111"
2
47
6
Returns: "001111 00000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000001111"
18
27
12
Returns: "000000000000111111 000000000000000000000000000111111 000000000000000000000000000"
32
30
43
Returns: "000000000000000000000000000000000000000000011 00000000000000000000000000000011 0000000000000000000000000000000000000000000"
31
24
2
Returns: "0000000000000000000000000000000 00000000000000000000000000000001111111111111111111111 001111111111111111111111"
40
24
31
Returns: "00000000000000000000000000000000000000001111111 0000000000000000000000000000000000000000 0000000000000000000000001111111"
36
26
37
Returns: "00000000000000000000000000000000000001111111111 000000000000000000000000001111111111 0000000000000000000000000000000000000"
18
17
46
Returns: "00000000000000000000000000000000000000000000001 000000000000000001 0000000000000000000000000000000000000000000000"
41
38
17
Returns: "00000000000000000000000000000000000000000 00000000000000000000000000000000000000000111111111111111111111 00000000000000000111111111111111111111"
48
20
29
Returns: "000000000000000000000000000000000000000000000000111111111 000000000000000000000000000000000000000000000000 00000000000000000000111111111"
34
3
50
Returns: "000000000000000000000000000000000000000000000000001111111111111111111111111111111 0001111111111111111111111111111111 00000000000000000000000000000000000000000000000000"
5
30
15
Returns: "000001111111111 000000000000000000000000000000 0000000000000000000000000000001111111111"
34
9
30
Returns: "0000000000000000000000000000000000111111111111111111111 0000000000000000000000000000000000 000000000111111111111111111111"
37
12
31
Returns: "00000000000000000000000000000000000001111111111111111111 0000000000000000000000000000000000000 0000000000001111111111111111111"
40
37
12
Returns: "0000000000000000000000000000000000000000 00000000000000000000000000000000000000001111111111111111111111111 0000000000001111111111111111111111111"
28
47
48
Returns: "000000000000000000000000000000000000000000000000 00000000000000000000000000001111111111111111111 0000000000000000000000000000000000000000000000001111111111111111111"
44
37
32
Returns: "00000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000011111 0000000000000000000000000000000011111"
9
49
50
Returns: "00000000000000000000000000000000000000000000000000 0000000001111111111111111111111111111111111111111 000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111"
45
30
5
Returns: "000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000001111111111111111111111111 000001111111111111111111111111"
35
48
36
Returns: "000000000000000000000000000000000001 000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000001"
13
19
6
Returns: "0000001111111 00000000000000000001111111 0000000000000000000"
16
37
14
Returns: "0000000000000011 000000000000000000000000000000000000011 0000000000000000000000000000000000000"
3
41
26
Returns: "00011111111111111111111111 00000000000000000000000000000000000000000 0000000000000000000000000000000000000000011111111111111111111111"
5
12
39
Returns: "000000000000000000000000000000000000000 000001111111 0000000000000000000000000000000000000001111111"
31
45
19
Returns: "0000000000000000000111111111111 000000000000000000000000000000000000000000000111111111111 000000000000000000000000000000000000000000000"
27
47
47
Returns: "00000000000000000000000000000000000000000000000 00000000000000000000000000011111111111111111111 0000000000000000000000000000000000000000000000011111111111111111111"
3
7
33
Returns: "000000000000000000000000000000000 0001111 0000000000000000000000000000000001111"
21
31
13
Returns: "000000000000011111111 000000000000000000000000000000011111111 0000000000000000000000000000000"
42
41
1
Returns: "000000000000000000000000000000000000000000 0000000000000000000000000000000000000000001111111111111111111111111111111111111111 01111111111111111111111111111111111111111"
30
50
48
Returns: "000000000000000000000000000000111111111111111111 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000111111111111111111"
50
13
3
Returns: "00000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000001111111111 0001111111111"
19
14
30
Returns: "00000000000000000000000000000011111 0000000000000011111 000000000000000000000000000000"
42
6
8
Returns: "00000000000000000000000000000000000000000011 000000000000000000000000000000000000000000 00000011"
17
3
47
Returns: "0000000000000000000000000000000000000000000000011111111111111 00011111111111111 00000000000000000000000000000000000000000000000"
34
26
4
Returns: "0000000000000000000000000000000000 00000000000000000000000000000000001111111111111111111111 00001111111111111111111111"
2
5
41
Returns: "00000000000000000000000000000000000000000 00111 00000000000000000000000000000000000000000111"
13
38
28
Returns: "0000000000000111111111111111 00000000000000000000000000000000000000 00000000000000000000000000000000000000111111111111111"
2
50
26
Returns: "00111111111111111111111111 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000111111111111111111111111"
1
50
50
Returns: "00000000000000000000000000000000000000000000000000 01111111111111111111111111111111111111111111111111 000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111"
1
1
50
Returns: "00000000000000000000000000000000000000000000000000 0 00000000000000000000000000000000000000000000000000"
1
1
1
Returns: "0 0 0"
50
1
1
Returns: "00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 0"
50
1
50
Returns: "000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111 01111111111111111111111111111111111111111111111111 00000000000000000000000000000000000000000000000000"
50
50
50
Returns: "11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111"
50
50
1
Returns: "01111111111111111111111111111111111111111111111111 000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111 00000000000000000000000000000000000000000000000000"
50
3
50
Returns: "0000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111 00011111111111111111111111111111111111111111111111 00000000000000000000000000000000000000000000000000"
3
1
1
Returns: "000 000 0"
10
8
4
Returns: "0000000000 00000000001111 00001111"
12
32
8
Returns: "000000001111 000000000000000000000000000000001111 00000000000000000000000000000000"
2
6
7
Returns: "0000000 001111 00000001111"
1
3
3
Returns: "000 011 00011"
1
2
2
Returns: "00 01 001"
8
2
7
Returns: "0000000011111 00000000 0011111"
2
2
1
Returns: "01 001 00"
1
4
1
Returns: "0 0000 0000"
4
1
3
Returns: "000011 0000 011"
3
2
1
Returns: "000 0001 01"
1
25
26
Returns: "00000000000000000000000000 0111111111111111111111111 00000000000000000000000000111111111111111111111111"
5
3
1
Returns: "00000 0000011 011"