Problem Statement
A string composed of the letters 'A' and 'B' is called beautiful if it satisfies all of the following criteria:
- it contains no more than countA occurences of 'A';
- it contains no more than countB occurences of 'B';
- each substring that contains only 'A's consists of no more than maxA characters;
- each substring that contains only 'B's consists of no more than maxB characters.
Given countA, countB, maxA and maxB, return the maximum possible length of a beautiful string.
Definition
- Class:
- BeautifulString
- Method:
- maximumLength
- Parameters:
- int, int, int, int
- Returns:
- int
- Method signature:
- int maximumLength(int countA, int countB, int maxA, int maxB)
- (be sure your method is public)
Constraints
- countA will be between 0 and 1000000, inclusive.
- countB will be between 0 and 1000000, inclusive.
- maxA will be between 0 and 1000000, inclusive.
- maxB will be between 0 and 1000000, inclusive.
Examples
0
0
10
10
Returns: 0
We don't have any available letters as countA=0 and countB=0, so the only beautiful string is the empty one.
10
10
0
0
Returns: 0
Now we have available letters, but can't include them into the beautiful string as maxA=0 and maxB=0.
3
5
1
1
Returns: 7
In this case we can't have two consecutive 'A's or 'B's, so letters in the beautiful string should alternate. If we start the string from 'A', the longest one we'll be able to get is "ABABAB". But if we start the string from 'B', we'll be able to get the longer one - "BABABAB".
677578
502524
989951
504698
Returns: 1180102
Here maxA >= countA and maxB >= countB, so we can easily construct a beautiful string using all available countA+countB letters.
0
0
0
0
Returns: 0
0
0
0
141786
Returns: 0
0
0
74408
0
Returns: 0
0
0
119881
462276
Returns: 0
0
157738
0
0
Returns: 0
0
145421
0
18972
Returns: 18972
0
5661
0
5661
Returns: 5661
0
161852
0
190827
Returns: 161852
0
383819
593664
0
Returns: 0
0
455228
19112
69172
Returns: 69172
0
3
4
3
Returns: 3
0
67627
343582
260263
Returns: 67627
34662
0
0
0
Returns: 0
232145
0
0
629896
Returns: 0
74102
0
43093
0
Returns: 43093
13251
0
727742
0
Returns: 13251
14422
0
14422
0
Returns: 14422
600836
0
28824
463349
Returns: 28824
50263
0
235862
180505
Returns: 50263
10700
0
10700
2311
Returns: 10700
285341
462664
0
0
Returns: 0
20405
283720
0
185820
Returns: 185820
129797
356059
0
373027
Returns: 356059
4
141464
0
24905
Returns: 24905
2
2
0
2
Returns: 2
2
3
0
1
Returns: 1
82211
107358
8387
0
Returns: 8387
202873
27000
205337
0
Returns: 202873
24104
1051
5
0
Returns: 5
5
9
5
0
Returns: 5
2
1
1
0
Returns: 1
72741
61024
66403
40152
Returns: 133765
387085
185394
4184
336687
Returns: 572479
6666
433973
104861
132944
Returns: 440639
90067
149593
178512
338128
Returns: 239660
5
1
7
1
Returns: 6
4855
2677
4855
1150
Returns: 7532
105
2713
916
19
Returns: 2119
386
283
386
416
Returns: 669
50696
671
9
102292
Returns: 6719
1
1
1
1
Returns: 2
735
734
1
398
Returns: 1469
32
31
31
31
Returns: 63
63995
45670
1
11904
Returns: 91341
1
2
2
1
Returns: 3
42
1
21
33
Returns: 43
3
1
1
1
Returns: 3
7
61
7
5
Returns: 47
313
407
97
1
Returns: 627
2
1
1
1
Returns: 3
1
2
1
1
Returns: 3
4
5
3
1
Returns: 9
1000000
1000000
1000000
1000000
Returns: 2000000
1
9
1
2
Returns: 5
4
49
52
5
Returns: 29
475
963
552
2
Returns: 1427
2028
6654
8225
2
Returns: 6086
1
99507
89823
11070
Returns: 22141
7395
452531
591053
44
Returns: 332819
7
1
1
4
Returns: 3
74
4
1
35
Returns: 9
802
13
38
451
Returns: 545
6831
357
12
5115
Returns: 4653
56683
282
26
90370
Returns: 7640
888375
84239
1
129170
Returns: 168479
10
6
8
1
Returns: 16
40
95
21
89
Returns: 135
123
151
549
775
Returns: 274
8841
9139
8112
2027
Returns: 17980
52876
19924
34100
99697
Returns: 72800
28181
579983
518744
741055
Returns: 608164
200
10
10
5
Returns: 120
15
5
5
5
Returns: 20
1111
2111
2222
9
Returns: 3222
7
6
1
3
Returns: 13
14
5
3
2
Returns: 19
7
10
1
3
Returns: 17
6
3
2
4
Returns: 9
3
6
3
2
Returns: 9
100
50
0
300
Returns: 50
524288
1000
1024
0
Returns: 1024
1
0
1
1
Returns: 1
12
4
2
2
Returns: 14
10
5
5
0
Returns: 5
7
2
3
2
Returns: 9
3
7
5
4
Returns: 10
200
700
500
250
Returns: 900
0
10
4
4
Returns: 4
13
3
3
3
Returns: 15
1000000
1000000
500000
20000
Returns: 2000000
0
1
0
1
Returns: 1
10
10
1
0
Returns: 1
32
12
0
2
Returns: 2
999999
99
1234
12
Returns: 123499
13
13
3
14
Returns: 26
1
1
0
5
Returns: 1
4
40
7
3
Returns: 19
5
0
5
0
Returns: 5
0
10
10
5
Returns: 5
0
0
0
5
Returns: 0
5
3
1
0
Returns: 1
4
4
3
1
Returns: 8
0
1
1
1
Returns: 1
1000
10000
10
9
Returns: 10009
300
100
300
1
Returns: 400
1
1
0
2
Returns: 1
19
21
9
20
Returns: 40
120000
100000
20000
10000
Returns: 220000
1
2
0
10
Returns: 2
1000000
999999
1000000
1
Returns: 1999999
15
17
2
3
Returns: 32
0
10
3
3
Returns: 3
12
12
10
0
Returns: 10
5
6
2
2
Returns: 11
10
10
2
10
Returns: 20
9
10
5
0
Returns: 5
999999
249987
7
5
Returns: 1249986
1000000
1000000
1000000
1
Returns: 2000000
10
1
3
0
Returns: 3
1000
50
1000
2
Returns: 1050
4
6
4
2
Returns: 10
9
2
3
3
Returns: 11
37
15
4
5
Returns: 52
5
3
1
2
Returns: 7
10001
10
100
10
Returns: 1110
5
100
3
3
Returns: 23
5
5
0
10
Returns: 5
1
5
0
9
Returns: 5
0
10
10
10
Returns: 10
0
10
1
2
Returns: 2
65536
10
65536
10
Returns: 65546
0
0
0
10
Returns: 0
10
0
10
0
Returns: 10
10
10
10
0
Returns: 10
1
7
7
0
Returns: 1
1
1
1
0
Returns: 1
0
1
0
2
Returns: 1
30
1
10
1
Returns: 21
1
2
0
1
Returns: 1
7
3
3
4
Returns: 10
10
1
0
10
Returns: 1
2
3
5
0
Returns: 2
2
0
4
0
Returns: 2
0
2
0
3
Returns: 2
10
0
8
3
Returns: 8
1
10
1
0
Returns: 1
3
4
2
2
Returns: 7
6
100
1
100
Returns: 106
2
1
0
3
Returns: 1
1000000
1000000
3
7
Returns: 2000000
0
10
0
20
Returns: 10
2
6
2
2
Returns: 8
65536
65536
65536
65536
Returns: 131072
5
5
0
2
Returns: 2
10
10
0
12
Returns: 10
5
3
5
1
Returns: 8
10
0
10
10
Returns: 10
10
10
2
0
Returns: 2
10
0
2
2
Returns: 2
5
4
4
1
Returns: 9
10
9
0
3
Returns: 3
20
5
1
30
Returns: 11
1
100
3
3
Returns: 7
100
20
15
10
Returns: 120
44
3
0
10
Returns: 3
15
4
0
2
Returns: 2
0
10
0
3
Returns: 3
9
10000
9
1000
Returns: 10009
1
10
0
1
Returns: 1
5
3
2
3
Returns: 8
10
10
1
1
Returns: 20
0
10
0
10
Returns: 10
3
16
2
5
Returns: 19
5
8
2
2
Returns: 13
0
5
0
6
Returns: 5
37
701
8
3
Returns: 151
100000
100000
4443
9997
Returns: 200000
3
20
3
4
Returns: 19
0
5
0
3
Returns: 3
1000000
100000
1000000
800
Returns: 1100000
987654
1000
100
100
Returns: 101100
63
45
39
9
Returns: 108
10
9
0
20
Returns: 9
645
6476
7
5
Returns: 3875
0
0
0
1000
Returns: 0
3
4
2
1
Returns: 7
5
3
2
1
Returns: 8
1
9
1
5
Returns: 10
2
0
0
4
Returns: 0
1000000
1005
2
3
Returns: 3017
100
5
10
2
Returns: 65
7
3
2
1
Returns: 10
1000000
1000000
10000
10000
Returns: 2000000
1000000
1000000
1000000
5
Returns: 2000000
901010
902130
632131
123
Returns: 1803140
10
10
0
100
Returns: 10
9475
2145
0
15
Returns: 15
10
10000
2
100
Returns: 1110
13
5
3
5
Returns: 18
24
4
5
1
Returns: 28
10
4
3
2
Returns: 14
1
5
1
1
Returns: 3
10
10
0
10
Returns: 10
100
100
1
2
Returns: 200
20
20
2
1
Returns: 40
0
3
0
5
Returns: 3
10
10
5
0
Returns: 5
677578
502524
5
404698
Returns: 1180102
10
10
3
2
Returns: 20
1
2
0
2
Returns: 2
5
10
2
1
Returns: 11
1
10000
1
1
Returns: 3
7
3
2
2
Returns: 10
3
5
2
1
Returns: 7
1
0
0
1
Returns: 0
0
1000
0
1
Returns: 1
1
100
1
100
Returns: 101
4
2
3
2
Returns: 6
5
3
0
1
Returns: 1
9
10
0
15
Returns: 10
15
3
3
3
Returns: 15
5
4
2
2
Returns: 9
10
1
1
1
Returns: 3
100
9
10
3
Returns: 109
20
5
5
3
Returns: 25
3
7
2
2
Returns: 10
1000
1000
2
1
Returns: 2000
900
800000
6
800
Returns: 721700
0
10
10
1000
Returns: 10
10
2
3
2
Returns: 11
5
7
3
6
Returns: 12
100
100
0
100
Returns: 100
4
2
1
2
Returns: 5
10
1000
1
1
Returns: 21
5
2
0
2
Returns: 2
100
8
10
10
Returns: 98
53
10
5
3
Returns: 63
999876
232
1
999567
Returns: 465
10
10
0
2
Returns: 2
10
20
0
2
Returns: 2
4
4
0
1
Returns: 1
11
3
2
4
Returns: 11
10001
5
0
10
Returns: 5
2000
1000
0
10
Returns: 10
9
10
1
10
Returns: 19
18
9
3
3
Returns: 27
3
3
0
0
Returns: 0
20
10
3
1
Returns: 30
999999
1000000
1
999999
Returns: 1999999
3
3
1
0
Returns: 1
1000
500
3
10
Returns: 1500
1000
1000
57
57
Returns: 2000
1000
5
3
3
Returns: 23
15
2
3
1
Returns: 11
1234
5
0
7
Returns: 5
3
5
0
1
Returns: 1
25
15
3
3
Returns: 40
100
1000
0
10000
Returns: 1000
1000
1000
1
1
Returns: 2000
3
15
10
5
Returns: 18
999999
2000
1000
12
Returns: 1001999
10000
1000
1000
1000
Returns: 11000
5
10
4
0
Returns: 4
50
10
10
1
Returns: 60
5
0
10
10
Returns: 5
5
4
5
0
Returns: 5
6
6
0
3
Returns: 3
4
12
3
3
Returns: 16
5
6
5
1
Returns: 11
7
7
2
2
Returns: 14
600
1000
57
57
Returns: 1600
5
5
2
2
Returns: 10
1000000
999999
5001
2008
Returns: 1999999
11
10
10
0
Returns: 10
75
55
0
31
Returns: 31
5
1
2
1
Returns: 5
99
102
0
5
Returns: 5
600000
600000
500000
500000
Returns: 1200000
4
9
4
2
Returns: 13
3
500
100
100
Returns: 403
5
1
0
4
Returns: 1
5
5
5
0
Returns: 5
100
10
0
1
Returns: 1
40000
100000
30000
90000
Returns: 140000
20
5
4
2
Returns: 25
100
100
0
50
Returns: 50
10
10
12
0
Returns: 10
100
1000
4
0
Returns: 4
478927
801804
10
10
Returns: 1280731
3
1
0
2
Returns: 1
1
4
0
5
Returns: 4
100
4
25
2
Returns: 104
1
1
0
1
Returns: 1
6
3
3
3
Returns: 9
1
1
0
3
Returns: 1
6
4
5
3
Returns: 10
1000000
100
100
100
Returns: 10200
100
30
0
50
Returns: 30
3
8
2
2
Returns: 11
10
10
8
0
Returns: 8
4
1
2
1
Returns: 5
0
100000
10
10
Returns: 10
10000
2000
3000
2000
Returns: 12000
100
50
2
1
Returns: 150
3
5
0
2
Returns: 2
1
100
2
2
Returns: 5
100
9
10
10
Returns: 109
1001
1001
2
2
Returns: 2002
9
2
3
10
Returns: 11
1000000
999
1
1
Returns: 1999
10
10
10
1
Returns: 20
5
17
1
3
Returns: 22
20
5
0
3
Returns: 3
10
6
2
6
Returns: 16
1000000
500000
333333
500000
Returns: 1500000
5
1
1
0
Returns: 1
0
6
0
10
Returns: 6
1000
11
5
5
Returns: 71
10
20
0
10
Returns: 10
5
0
4
1
Returns: 4
10
2
3
5
Returns: 11
5
2
1
1
Returns: 5
1000
100
5
5
Returns: 605
100
10
1
2
Returns: 21
3
1
2
0
Returns: 2
1000
2000
6
8
Returns: 3000
1000000
77777
1
13
Returns: 155555
677578
999999
25
99999
Returns: 1677577
3
5
7
0
Returns: 3
46340
1000000
1000000
46341
Returns: 1046340
15
4
5
2
Returns: 19
2
4
0
5
Returns: 4
100
10
5
10
Returns: 65
100
49
2
1000
Returns: 149
5
7
5
3
Returns: 12
3
3
1
3
Returns: 6
3
8
4
2
Returns: 11
1000000
1000000
1000000
50000
Returns: 2000000
30
3
7
7
Returns: 31
16
16
0
5
Returns: 5
9
2
3
0
Returns: 3
3
5
10
1
Returns: 7
20
20
5
1
Returns: 40
1000
10
10
10
Returns: 120
3
2
1
0
Returns: 1
262144
65536
65536
1
Returns: 327680
1001
1001
1
2
Returns: 2002
0
100
0
1000
Returns: 100
1000
3
10
10
Returns: 43
5
12
3
3
Returns: 17
999999
559845
70
1000000
Returns: 1559844
7
10
4
2
Returns: 17
2
6
2
3
Returns: 8
3
3
2
2
Returns: 6
1
41
18
23
Returns: 42
1000000
40000
49
2
Returns: 1040000