In this HackerEarth Jumping Tokens problem solution, 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:
  1. R x B -> xR
  2. B x R -> xB
  3. R x B -> Bx
  4. B x R -> 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.


HackerEarth Jumping Tokens problem solution


HackerEarth Jumping Tokens problem solution.

import java.util.Scanner;
public class JumpingTokens {
    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while(t-->0) {
            String s = in.next();
            if (s.equals("RBBBR") || s.equals("BRRRB")) {
                System.out.println(3);
                continue;
            }
            char[] c = s.toCharArray();
            int n = c.length;
            int countR = 0, countB = 0;
            boolean alternating = true;
            int ridx = 0, bidx = 0;
            for (int i = 0; i < c.length; i++) {
                if (c[i] == 'R') {countR++; ridx = i;}
                else {countB++; bidx = i;}
                if (i > 0 && c[i] == c[i-1]) alternating = false;
            }
            if (alternating || countR == 0 || countB == 0) {
                System.out.println(n);
                continue;
            }
            if (countR == 1) {
                System.out.println((ridx % 3 == (c.length - ridx - 1) % 3) ? 3 : 2);
                continue;
            }
            if (countB == 1) {
                System.out.println((bidx % 3 == (c.length - bidx - 1) % 3) ? 3 : 2);
                continue;
            }
            System.out.println(2);
        }
    }
}