Problem Brief

Maximum Number of Workers with Equal Left and Right Shoes

INTERNOA

Ellen would like to assign this task to her subordinate workers. Each worker should get a distinct interval of adjacent shoes, such that the number of left shoes is equal to the number of right shoes. Each shoe must be assigned to exactly one worker.

What is the maximum number of workers that Ellen can assign to this task?

Write a function:

class Solution { public int solution(String S); }

that, given a string S of letters "L" and "R", denoting the types of shoes in line (left or right), returns the maximum number of intervals such that each interval contains an equal number of left and right shoes.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [2..100,000];

String S is made only of the characters 'R' and/or 'L';

The number of letters "L" and "R" in string S is the same.

Another problem from the same batch:

1Example 1

Input

S = "RLRRLLRLRRLL"

Output

Explanation

Because S can be split into intervals: "RL", "RRLL", "RL" and "RRLL". Note that the intervals do not have to be of the same size.

2Example 2

Input

S = "RLLLRRRLLR"

Output

Explanation

The function should return 4, because S can be split into intervals: "RL", "LLRR", "RL" and "LR".

3Example 3

Input

S = "LLRLRLRLRLRLRR"

Output

Explanation

The function should return 1.