### chinesecoder's blog

By chinesecoder, history, 9 months ago, ,

The problem , 814c , my approach was , for each segment [l, r ] , check whether its possible to color it with at most m colors or not.

since there can be 26*n queries and n^2 segments , the solution will work in 26*n^3 which will give TLE .

The editorial mentions some prefix based approach but i couldn't understand the 2nd part , how its optimizing the solution .

How to reduce 26 * n ^3 to 26*n ^2 .

is there any dp solution possible to it . ?

• -14

 » 9 months ago, # | ← Rev. 3 →   0 let f(l) be the biggest r that you can color [l, r] with at most m colors. then it's clear that if l1 ≤ l2 then f(l1) ≤ f(l2). so you can find answer for all queries in O(n) with two-pointer.I think this solution works too:let DP[i][j][c] be maximum number of continuous character of c ending at i if we color exactly j characters. then DP[i][j][c] is equal to DP[i - 1][j][c] + 1 if s[i] = c and DP[i - 1][j - 1][c] otherwise.
•  » » 9 months ago, # ^ |   0 Thanks , two pointer method is quite tough to implement . in 2nd method do we have to add any more coding or they r sufficient.LordAlbusDumbledore
•  » » » 9 months ago, # ^ |   0 For every query mi ci, you should get the maximum value for every 1 ≤ i ≤ n: DP[i][min(n, mi)][ci].
•  » » » » 9 months ago, # ^ |   0 Thanks LordAlbusDumbledore
 » 9 months ago, # |   0 Here is my approach as requested.Let f(x, r) represent the maximum length of substring of character x with EXACTLY r replacements. How do we calculate it for a given x ? We visit every range [L, R]. The number of replacements in this range is the number of characters that are not x.  for(int ch = 0; ch < MAX_ALPHABETS; ch++) { for(int left = 0; left < length; left++) { int replacements = 0; for(int right = left; right < length; right++) { replacements += (S[right] != 'a' + ch); maximum_segment[ch][replacements] = max(maximum_segment[ch][replacements], right - left + 1); } } } This takes O(σ N2)Now let g(x, r) represent the maximum length of string if we do at most r replacements.g(x, r) = max{f(x, 0), f(x, 1), f(x, 2), ... , f(x, r)}  for(int ch = 0; ch < MAX_ALPHABETS; ch++) { for(int replacements = 1; replacements <= length; replacements++) { maximum_segment[ch][replacements] = max(maximum_segment[ch][replacements], maximum_segment[ch][replacements - 1]); } } 
•  » » 9 months ago, # ^ |   0 Thanks for the nice approach .