Purple Rain

This problem gives us a list of R and B and asks us for the range which has the greatest difference in counts between the two.

It should be clear from the 10^5 limit, that an n^2 brute force solution is too slow. Our solution will have to be linear, perhaps with a logn.

We can simplify the problem by first asking which range the most R-B, and then doing the same for B-R, choosing whichever is best. This slightly simplifies the problem. If we are solving for R-B, we can deduce a really simple rule:

• If the "candidate" range has a B on the end, we can remove that element from the range and the range will be "more" optimal

This can be generalized a bit further intuitively

• If the first k characters of a range have more B's in it than R's, we can remove it and the range will be more optimal.

This leads to a greedy solution:

1. Assume the entire input is the optimal solution
2. Walk from the front, keeping track of the number of B's and R's encountered
3. If the number of B's is ever greater than the number of R's, then "chop" that bit off the range, and start walking from the chop point
4. repeat from the back

We then repeat the process, optimizing for B instead of R, and take the max. The process is linear.

Clever Solution

We can assume ever R is a +1 and every B is a -1, and compute the prefix sum of the entire input (the sum of all values before a given element). This prefix sum can be computed in linear time (just walk the list and keep track as you go!). The solution will be the elements with the greatest and smallest prefix sums.

Implementation notes

Due to the output rules, we have to be a little careful. In the first solution, this means when "chopping" from the back of the list, we chop if the count of B and R is equal. This doesn't make a more optimal range, but it ensures we get the "westernmost" ending point. The same rule applies for the clever solution. In the case of ties, take the leftmost element with the given extrema.

If using the first solution, we can encode B and R as + and -1, and check for sign to chop, instead of explicitly counting the number of each letter. We can also literally exchange B and R in the string for the second run without changing the rest of the code, simplifying things.

import java.util.*;
public class c {
	static Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		char[] a=in.next().toCharArray();
		int[] ans= {0,0,0};
		for(int i=0;i<2;i++) {
			int end=a.length-1,sum=0,endans=a.length-1,start=0,startans=0;
			while(end>0) {
				sum+=a[end--]=='B'?1:-1;
				if (sum<=0) {
					sum=0;
					endans=end;
				}
			}
			sum=0;
			while(start<=endans) {
				sum+=a[start++]=='B'?1:-1;
				if (sum <0) {
					sum=0;
					startans=start;
				}
			}
			for(start=startans,sum=0;start<=endans;start++)sum+=a[start]=='B'?1:-1;
			if(sum>ans[0]||(sum==ans[0]&&(startans<ans[1]||(startans==ans[1]&&endans<ans[2])))) {
				ans[0]=sum;
				ans[1]=startans;
				ans[2]=endans;
			}
			for(int j=0;j<a.length;j++)a[j]=a[j]=='B'?'R':'B';
		}
		System.out.printf("%d %d\n",ans[1]+1,ans[2]+1);
	}
}