Jake and Cake
InterviewTime limit1sMemory limit128 MB
Cut a row cake at the fewest boundaries so each person gets N/4 strawberries and N/4 kiwis, and output one such cutting.
- Level
Medium5 of 10
- Topics
- Brute force, Implementation, Greedy, Two pointers
- Solved
- No attempts yet
Problem
Jake received a long cake as a gift from Rainicorn.
N pieces of fruit are placed on the cake in a single row at equal intervals. The fruits consist of N/2 strawberries and N/2 kiwis, and N is a multiple of 4.
Jake wants to split the cake with Finn so that each of them eats exactly half, fruit included. Since the types of fruit matter, Jake must receive N/4 strawberries and N/4 kiwis. Finn must also receive the same number of strawberries and kiwis as Jake.
Jake and Finn find cutting the cake a nuisance, so they want to minimize the number of cuts. Given the cake, tell them the minimum number of cuts needed to divide it equally between Finn and Jake, and one way to make those cuts.
Input
The first line gives the number of fruits on the cake, N (4 ≤ N ≤ 200,000).
The second line gives a string of length N describing the cake. If the i-th character is 's', the i-th position holds a strawberry; if it is 'k', it holds a kiwi.
Output
Print the minimum number of cuts k (1 ≤ k ≤ N - 1) on the first line.
On the second line, print k integers c1, c2, ..., ck (1 ≤ c1 < c2 < ... < ck ≤ N - 1). Here ci means cutting between the ci-th fruit and the (ci+1)-th fruit.
If there are several ways to cut, print any one of them.