All Tracks Basic Programming Implementation Basics of Implementation Problem

Jumping Tokens
Tag(s):

Medium, ad hoc, approved

Problem
Editorial
Analytics

You are given a row of $$n$$ tokens in a row colored red and blue.

In one move, you can choose to perform a capture. A capture chooses a token, and makes a jump over exactly one other token, and removes a token of the opposite color.

More specifically, given three adjacent tokens we can convert it into the following state with two adjacent tokens:

  • $$RxB \to xR$$
  • $$BxR \to xB$$
  • $$RxB \to Bx$$
  • $$BxR \to Rx$$
where x is a token of an arbitrary color.

Given the initial row of tokens, return the minimum possible length of the resulting row after a series of captures.

Input Format:

The first line will contain the number of test cases $$T$$.
Each test case can be described with one line.
This line will contain a string consisting of only characters 'R' and 'B' denoting the colors in the row.

Output Format:

Output $$T$$ numbers, the answers to each problem.

Constraints

There is no partial credit for this problem.

There is only one file for this problem. The file has the following constraints.
$$T = 1000$$
$$1 ≤ n ≤ 50$$

SAMPLE INPUT
6
RB
RBB
BBRRB
RRR
BBBRRRB
RBRRRBR
SAMPLE OUTPUT
2
2
2
3
2
2
Explanation

In the first sample, there are no possible captures we can perform.

In the second sample, we can perform a capture with the red token to get the state $$BR$$.

In the third sample, we can apply the following captures $$BB\hat{R}RB \to \hat{B}BRR \to BB\hat{R} \to RB$$. The hat denotes which token is doing the capture in the next step.

For the fourth sample, we can't do any captures.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

December Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications