RANDG - Red And Green

You have several squares arranged in a single row. Each square is currently painted red or green. You can choose any of the squares and paint it over with either color. The goal is that, after painting, every red square is further to the left than any of the green squares. We want you to do it repainting the minimum possible number of squares.

Squares are numbered from left to right. You will be given the initial arrangement as a String, such that character i is 'R' if square i is red or 'G' if square i is green. Print the minimum number of repaints needed to achieve the goal.

Input

There will be several test cases. Each test case will contain a string of not more than 50 characters on a separate line. Input is terminated by EOF.

Output

For each test case, print the output on a separate line.

Constraints

Input will contain between 1 and 50 characters, inclusive.

Each character of input will be either 'R' or 'G'.

Sample

Input
RGRGR
RRRGGGGG
GGGGRRR
RGRGRGRGRGRGRGRGR

Output
2
0
3
8

Solution & Dataset: Bidhan Roy


Added by:Bidhan
Date:2012-10-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Topcoder

hide comments
2016-09-27 14:16:38 Abhishek

Edit : okay done! , WA for some silly mistake, done in O(n) , either the size or the time limit should be strict,

Last edit: 2016-09-27 14:20:04
2015-12-13 22:05:58
strings could have been longer, the most naive brute-force solution gets AC in 0.00 :/
2013-12-23 14:59:36 Jumpy
got AC 0.00 sec but not content with that still looking forward to new logic....
2013-12-11 09:52:46 Andrey Maksimenko
Nirmal: you should repaint all red squares, so you will get GGGGGGG.
2013-12-02 20:32:09 Nirmal
i could't understand third test case.. someone help me .. GGGGRRR
2013-09-07 10:58:17 Trilok Sharma
Test Case:
RRGRRRGGRGG
2
2013-05-28 17:22:32 nitish rao
@Roy ... can you check my submission and hint me where am i going wrong.. Id:9370526

Last edit: 2013-05-29 03:51:51
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.