longest consecutive sequence of same character in string by replacing m characters?

general
, , ,
1

Please help me solving Monk and Chocolates problem on Hackerearth, this problem is based on strings.

2

This is a copied question and original question is here http://codeforces.com/contest/814/problem/C

You can find the editorial here http://codeforces.com/blog/entry/52449

3

@hruday968
The editorial there is not much detailed, can you please explain it in more detail.

4

@vijju123 @mathecodician

guys help me out.

5

(Let (1-26) denote the range (a-z) and (27-52) denote (A-Z) )Let a be the original array given by the question.make an array presum[52][N], where presum[l][i] denotes number of times letter l has occurred in the range a[1]…to a[i].

Now starts the solution- for every index i we will find the maximum length of similar chocolate segment we can make whose ending index is i.

Now we have the ending index(which is i), to find the starting index of the longest segment we will do binary search. The binary search should be done in the range 0 to i-1. while doing binary search to check if an index j is feasible or not for the starting point of the longest segment we will do the following -

temp=0;
for(int m=1;m<=52;m++)
temp = max(ans, s[m][i]-s[m][j]);

if ( (i-j)-temp <= M ) return true;
else return false;

Here in the code M denotes the maximum number of magical changes we can do(as mentioned in the question).

If the above code seems alien to you, i am explaining it to you- we are finding maximum number of same letter in the range (i,j) using the for loop(variable temp stores it in the code). (i-j) -temp denotes the remaining letter not considering the max-occurred letter, which should be <= M to make the range (i,j) to same letter. if it is greater than M we cannot change it.

For every i we have counted the maximum length of segment, now print the maximum over-all $i’$s.

feel free to ask any further doubts.

for every i we do at max 52logN iteration. so it is order of O(NlogN) with a constant factor > 52.

I have also found a solution where the constant is 2 :P. but the time limit is 4 seconds so 52 will work undoubtedly. :D. I must admit there may be a better (may be a linear time) solution(may be…o.O)…

6

@abhikalpu_123

Can you please tell, what logic is used here

https://pastebin.com/CvaXitxP

It works without any extra space.

7

@vijju123

can you check the solution on the link in above mentioned comment and figure out what is the logic being used there for this problem.

8

Sorry, i just saw this Q. Fine, give me some time.

9

The solution is quite easy to understand. The only block of code you need to understand is in fnction solve, and its this-

for (int c = 0; c < 26; ++c) {
            int letterCount = 0,nonLetterCount = 0;
            int remove = 0;
            for (int k = 0; k < chocolateString.length(); ++k) {
 
                if(chocolateString.charAt(k) == (char)(c + 'a')){
                    letterCount++;
                }
                else
                    nonLetterCount++;
 
                if (nonLetterCount <= magicMoves) {
                    ans = max(ans, nonLetterCount + letterCount);
                }
                else {
                    if(chocolateString.charAt(remove++) == (char) (c + 'a')){
                        letterCount--;
                    }
                    else
                        nonLetterCount--;
                }
            }

The outer loop is used, as you must have perceived, to make out all 26 lowercase letters from a to z. Then, for each letter, it will do the following-

  1. Reset the letter and non letter count to 0 for that letter. Lets call it ch for reference. Then it will enter the inner loop.
  2. Check if letter at this index is equal to ch or not. It will increase count accordingly.
  3. Check if we have surplus magic moves to convert this entire range to ‘ch’ . If yes, then we update the answer by max of what it was before, to the count. NOTE- We have not yet traversed the entire string length. For every index i, if we have surplus magic move, answer is updated.
  4. Now lets say we ran out of magic moves. Then of course, we cannot convert this entire range to ch. Now this guy used the SLIDING window concept. The first thing we must recognize is that, if for a range [L,R], we are short of magic moves, then we will be short of magic moves for any range [L,R+K] , where K is a positive constant. Meaning, if this range cannot be entirely converted to ch, then any ranger bigger than this, starting from same index, can also not be entirely converted to ch. So we need not compute any further on ranges starting from index i.
  5. So what does this mean? This means we should move our “window” forward. By that remove, we update the letter and non-letter variables as if we started from index ‘i+1’ instead of index i. If we have surplus magic moves now, then we update answer, else we keep on moving window forward until we have enough magic moves to convert our new range [L2,R] to ch.
  6. In other terms, till we have surplus magic moves, we expand our window from the END (or right side) and if we run out of magic moves, we contract the window from START (left). This is equivalent to “sliding” a window in real life, and hence the name.
  7. At any point of time, we are making sure that our window size is enough to convert entire range enclosed by it to ch. Hence, any answer is updated only if we have enough magic moves, else range is adjusted till we have enough magic moves.

Get back to me incase of doubt.