Question 1 — N boxes are Arrranged in a line. Each box is colored either with white or black. You can select any number of boxes from the starting and put it behind the last box in the same sequence as it was placed initially. you can perform this operation atmost once. For example string s="wbbb" . In one operation you can select "wb" and from the start and put it behind the last box "b".

Note: you cannot select all the n boxes.

You are required to find the minimum number of boxes whose colors must be reversed so that all the boxes in the sequence are of an alternate color, that is any two adjacent boxes are of different colors.

Input : 5
wwwwwbbww
wwwb
bwww
wwww
bbbbb
Output :
3
1
1
2
2

I was thinking of brute forcing the solution, that is doing operation for each length and then calculating for that configuration. Can anyobody tell the correct approach

Append string to itself and use sliding window of size N , and calculate each window the transition required to convert, now while moving the window you could also manage the dp states , dp will be minimum operation required to convert current window that is ending at index i and such that ith character is W or B, and before that there is alternating sequence for the range [i-N+1,i].

Let

`pref[i][0]`

show the minimum number of flips to make the characters`[0, i)`

alternating while the first character itself being`W`

.`pref[i][1]`

shows the same thing but the first character needs to be a`B`

there. Do this calculation for all suffix too, where`suff[i][0]`

shows the characters`[i, n)`

alternating while the last one is`W`

and`suff[i][1]`

for the last one being`B`

. Those calculations are`O(n)`

. Then the answer is minimum of`min(pref[i][0] + suff[i+1][0] + 1, pref[i][1] + suff[i+1][0], pref[i][0] + suff[i+1][1], pref[i][1] + suff[i+1][1] + 1)`

for all`i`

. This is also`O(n)`

.I want to ask you 2 things:-

`pref[i]`

contains`[0,i)`

while`suff[i]`

contains`[i,n)`

and in the end you're checking for`pref[i]+suff[i+1]`

, which means you're not considering`ith`

character at all.`'W'`

to an alternating suffix which ends with`'W'`

(for ex`...BWBWBW + WBWBWB...`

) then I believe the characters of at least one of the string should be flipped (i.e.`...BWBWBW + BWBWBW...`

or`...WBWBWB + WBWBWB...`

) which may cost more than 1 depending on the`length`

and values of`pref[i] and suff[i].`

Please correct me If I'm wrong or If I missed something.

Correct, my bad.

Should be

`pref[i]+suff[i]`

Now I think about it, I believe you don't need to check for +1 cases (do you? I might look into it later).

I think we need to consider them. And the cost should depend on the relation between two numbers

`X`

and`Y`

where`X is number of operations required to form an alternating string S`

while`Y is the number of operations required to from the counter alternating string of S`

(Sorry couldn't find a better word) and If I'm not wrong, the relation should be`Y = len(S)-X.`

Can anyone verify if my code is right? Or missing some edge cases?

My idea: lets take

`wwwb`

as e.g. Moving prefix back is essentially duplicating the front part back which gives me the string`wwwbwww`

. The target strings are`wbwbwbw`

or`bwbwbwb`

Using sliding widown we calculate the min of changes.Codeit's very easy

1. pre-compute suffix array cost making wbwbwb and bwbwbw.

-> ans = min(ans ,prefix cost of starting with w and prefix end with b )

-> ans = min(ans ,prefix cost of starting with b and prefix end with w )

codevoid solve(){

}

What we can do is brute force the solution. We can one by one remove from the i length substring from the beginning and add it to the end, not in the literal sense but we can simulate so by keeping count of the number of black and white balls present in the even and odd positions. And suppose the original string is bwwwb. (consider 1 indexing) odd => b = 2 , w = 1 even => b = 0, w = 2 If we remove substring of length 1, then the string will become wwwbb and even=> b = 1 , w = 1 odd=> b = 1, w = 2 . We can calculate them easily by keeping prefix sums of black and white respecitvely. And for each configuration, we can calculate the answer for that configuration by min(even) + min(odd)

And we take minimum for all possible configutations

time complexity : O(n)