|
1 | 1 | packageg3401_3500.s3441_minimum_cost_good_caption; |
2 | 2 |
|
3 | | -// #Hard #String #Dynamic_Programming #2025_02_04_Time_48_ms_(96.00%)_Space_56.50_MB_(89.33%) |
| 3 | +// #Hard #String #Dynamic_Programming #2025_03_13_Time_20_ms_(100.00%)_Space_46.12_MB_(96.53%) |
4 | 4 |
|
5 | | -@SuppressWarnings({"java:S107","java:S6541"}) |
6 | | -publicclassSolution { |
7 | | -privatestaticfinalintINF =Integer.MAX_VALUE /2; |
| 5 | +importjava.util.Arrays; |
8 | 6 |
|
| 7 | +publicclassSolution { |
9 | 8 | publicStringminCostGoodCaption(Stringcaption) { |
10 | 9 | intn =caption.length(); |
11 | 10 | if (n <3) { |
12 | 11 | return""; |
13 | 12 | } |
14 | | -char[]arr =caption.toCharArray(); |
15 | | -int[][]prefixCost =newint[n +1][26]; |
16 | | -for (inti =0;i <n;i++) { |
17 | | -intorig =arr[i] -'a'; |
18 | | -for (intc =0;c <26;c++) { |
19 | | -prefixCost[i +1][c] =prefixCost[i][c] +Math.abs(orig -c); |
20 | | - } |
21 | | - } |
22 | | -int[]dp =newint[n +1]; |
23 | | -int[]nextIndex =newint[n +1]; |
24 | | -int[]nextChar =newint[n +1]; |
25 | | -int[]blockLen =newint[n +1]; |
26 | | -for (inti =0;i <n;i++) { |
27 | | -dp[i] =INF; |
28 | | -nextIndex[i] = -1; |
29 | | -nextChar[i] = -1; |
30 | | -blockLen[i] =0; |
31 | | - } |
32 | | -dp[n] =0; |
33 | | -for (inti =n -1;i >=0;i--) { |
34 | | -for (intl =3;l <=5;l++) { |
35 | | -if (i +l <=n) { |
36 | | -intbestLetter =0; |
37 | | -intbestCost =INF; |
38 | | -for (intc =0;c <26;c++) { |
39 | | -intcostBlock =prefixCost[i +l][c] -prefixCost[i][c]; |
40 | | -if (costBlock <bestCost) { |
41 | | -bestCost =costBlock; |
42 | | -bestLetter =c; |
43 | | - } |
44 | | - } |
45 | | -intcostCandidate =dp[i +l] +bestCost; |
46 | | -if (costCandidate <dp[i]) { |
47 | | -dp[i] =costCandidate; |
48 | | -nextIndex[i] =i +l; |
49 | | -nextChar[i] =bestLetter; |
50 | | -blockLen[i] =l; |
51 | | - }elseif (costCandidate ==dp[i]) { |
52 | | -intcmp = |
53 | | -compareSolutions( |
54 | | -nextChar[i], |
55 | | -blockLen[i], |
56 | | -nextIndex[i], |
57 | | -bestLetter, |
58 | | -l, |
59 | | - (i +l), |
60 | | -nextIndex, |
61 | | -nextChar, |
62 | | -blockLen, |
63 | | -n); |
64 | | -if (cmp >0) { |
65 | | -nextIndex[i] =i +l; |
66 | | -nextChar[i] =bestLetter; |
67 | | -blockLen[i] =l; |
68 | | - } |
69 | | - } |
| 13 | +byte[]s =caption.getBytes(); |
| 14 | +int[]f =newint[n +1]; |
| 15 | +f[n -1] =f[n -2] =Integer.MAX_VALUE /2; |
| 16 | +byte[]t =newbyte[n +1]; |
| 17 | +byte[]size =newbyte[n]; |
| 18 | +for (inti =n -3;i >=0;i--) { |
| 19 | +byte[]sub =Arrays.copyOfRange(s,i,i +3); |
| 20 | +Arrays.sort(sub); |
| 21 | +bytea =sub[0]; |
| 22 | +byteb =sub[1]; |
| 23 | +bytec =sub[2]; |
| 24 | +bytes3 =t[i +3]; |
| 25 | +intres =f[i +3] + (c -a); |
| 26 | +intmask =b <<24 |s3 <<16 |s3 <<8 |s3; |
| 27 | +size[i] =3; |
| 28 | +if (i +4 <=n) { |
| 29 | +byte[]sub4 =Arrays.copyOfRange(s,i,i +4); |
| 30 | +Arrays.sort(sub4); |
| 31 | +bytea4 =sub4[0]; |
| 32 | +byteb4 =sub4[1]; |
| 33 | +bytec4 =sub4[2]; |
| 34 | +byted4 =sub4[3]; |
| 35 | +bytes4 =t[i +4]; |
| 36 | +intres4 =f[i +4] + (c4 -a4 +d4 -b4); |
| 37 | +intmask4 =b4 <<24 |b4 <<16 |s4 <<8 |s4; |
| 38 | +if (res4 <res ||res4 ==res &&mask4 <mask) { |
| 39 | +res =res4; |
| 40 | +mask =mask4; |
| 41 | +size[i] =4; |
70 | 42 | } |
71 | 43 | } |
72 | | - } |
73 | | -if (dp[0] >=INF) { |
74 | | -return""; |
75 | | - } |
76 | | -StringBuilderbuilder =newStringBuilder(n); |
77 | | -intidx =0; |
78 | | -while (idx <n) { |
79 | | -intlen =blockLen[idx]; |
80 | | -intc =nextChar[idx]; |
81 | | -for (intk =0;k <len;k++) { |
82 | | -builder.append((char) ('a' +c)); |
83 | | - } |
84 | | -idx =nextIndex[idx]; |
85 | | - } |
86 | | -returnbuilder.toString(); |
87 | | - } |
88 | | - |
89 | | -privateintcompareSolutions( |
90 | | -intoldLetter, |
91 | | -intoldLen, |
92 | | -intoldNext, |
93 | | -intnewLetter, |
94 | | -intnewLen, |
95 | | -intnewNext, |
96 | | -int[]nextIndex, |
97 | | -int[]nextChar, |
98 | | -int[]blockLen, |
99 | | -intn) { |
100 | | -intoffsetOld =0; |
101 | | -intoffsetNew =0; |
102 | | -intcurOldPos; |
103 | | -intcurNewPos; |
104 | | -intletOld =oldLetter; |
105 | | -intletNew =newLetter; |
106 | | -intlenOld =oldLen; |
107 | | -intlenNew =newLen; |
108 | | -intnxtOld =oldNext; |
109 | | -intnxtNew =newNext; |
110 | | -while (true) { |
111 | | -if (letOld !=letNew) { |
112 | | -return (letOld <letNew) ? -1 :1; |
113 | | - } |
114 | | -intremainOld =lenOld -offsetOld; |
115 | | -intremainNew =lenNew -offsetNew; |
116 | | -intstep =Math.min(remainOld,remainNew); |
117 | | -offsetOld +=step; |
118 | | -offsetNew +=step; |
119 | | -if (offsetOld ==lenOld &&offsetNew ==lenNew) { |
120 | | -if (nxtOld ==n &&nxtNew ==n) { |
121 | | -return0; |
122 | | - } |
123 | | -if (nxtOld ==n) { |
124 | | -return -1; |
| 44 | +if (i +5 <=n) { |
| 45 | +byte[]sub5 =Arrays.copyOfRange(s,i,i +5); |
| 46 | +Arrays.sort(sub5); |
| 47 | +bytea5 =sub5[0]; |
| 48 | +byteb5 =sub5[1]; |
| 49 | +bytec5 =sub5[2]; |
| 50 | +byted5 =sub5[3]; |
| 51 | +bytee5 =sub5[4]; |
| 52 | +intres5 =f[i +5] + (d5 -a5 +e5 -b5); |
| 53 | +intmask5 =c5 <<24 |c5 <<16 |c5 <<8 |t[i +5]; |
| 54 | +if (res5 <res ||res5 ==res &&mask5 <mask) { |
| 55 | +res =res5; |
| 56 | +mask =mask5; |
| 57 | +size[i] =5; |
125 | 58 | } |
126 | | -if (nxtNew ==n) { |
127 | | -return1; |
128 | | - } |
129 | | -curOldPos =nxtOld; |
130 | | -letOld =nextChar[curOldPos]; |
131 | | -lenOld =blockLen[curOldPos]; |
132 | | -nxtOld =nextIndex[curOldPos]; |
133 | | -offsetOld =0; |
134 | | -curNewPos =nxtNew; |
135 | | -letNew =nextChar[curNewPos]; |
136 | | -lenNew =blockLen[curNewPos]; |
137 | | -nxtNew =nextIndex[curNewPos]; |
138 | | -offsetNew =0; |
139 | | - }elseif (offsetOld ==lenOld) { |
140 | | -if (nxtOld ==n) { |
141 | | -return -1; |
142 | | - } |
143 | | -curOldPos =nxtOld; |
144 | | -letOld =nextChar[curOldPos]; |
145 | | -lenOld =blockLen[curOldPos]; |
146 | | -nxtOld =nextIndex[curOldPos]; |
147 | | -offsetOld =0; |
148 | | - }elseif (offsetNew ==lenNew) { |
149 | | -if (nxtNew ==n) { |
150 | | -return1; |
151 | | - } |
152 | | -curNewPos =nxtNew; |
153 | | -letNew =nextChar[curNewPos]; |
154 | | -lenNew =blockLen[curNewPos]; |
155 | | -nxtNew =nextIndex[curNewPos]; |
156 | | -offsetNew =0; |
157 | 59 | } |
| 60 | +f[i] =res; |
| 61 | +t[i] = (byte) (mask >>24); |
| 62 | + } |
| 63 | +StringBuilderans =newStringBuilder(n); |
| 64 | +for (inti =0;i <n;i +=size[i]) { |
| 65 | +ans.append(String.valueOf((char)t[i]).repeat(Math.max(0,size[i]))); |
158 | 66 | } |
| 67 | +returnans.toString(); |
159 | 68 | } |
160 | 69 | } |