Analysis

Given an input string ~wwwbbrwrbrbrrbrbrwrwwrbwrwrrb~, we concatenate it with itself, result in ~wwwbbrwrbrbrrbrbrwrwwrbwrwrrbwwwbbrwrbrbrrbrbrwrwwrbwrwrrb~. This trick, working on handling minus or over-length index is easier.

Brute force solution.

For each index ~a_i~ as a start, if ~a_{i+1}~ can be picked into the longest substring, we pick it then do this again on ~a_{i+1}~. Note that, if ~a_i~ is w, we must treat it as b and r, one by one. We do ~N~ times of picking attempt for each ~a_i~. Therefore complexity is ~O(N^2)~. Just a straight forward solution.

DP solution.

• We denote substring composed by successive ~r~, which ends at index ~i~ to ~t_{i,r}~.
• Similarly, we denote substring composed by successive ~b~, which ends at index ~i~ to ~t_{i,b}~.
• On the other hand, we denote substring composed by successive ~r~, which starts at index ~i~ to ~s_{i,r}~.
• And substring composed by successive b, which starts at index ~i~ to ~t_{i,b}~.

For each index ~a_i~, ~\max \{s_{i,r}, s_{i,b} \} + \max \{t_{i,r}, t_{i,b} \}~ is the length of longest substring if we break it at index ~i~. We do this for ~N~ times, the greatest one is the answer. Complexity of this algorithm is ~O(n)~.