FastPrep
Problem · String

Balance the Game Board

● MediumMicrosoftFULLTIMEOA
See Microsoft hiring insights

A game board consists of N+1 fields, numbered from 0 to N from left to right. One letter ("a" or "b") is written between every two adjacent fields. The letters on the board are described by a string L of length N, where L[K] (for K within the range [0..N-1]) is the letter between fields K and K+1.

For example, given L = "aaabab" and N = 6, the game board at the beginning looks like this:

a a a b a b

0 1 2 3 4 5 6

A game piece is placed at start. It can move left or right, flipping the letter it crosses ("a" → "b" and "b" → "a"). The objective is to find the minimum number of moves needed to balance the count of "a" and "b". If it's impossible, return -1

Write a function that, given a string L of length N and an integer start, returns the minimum number of moves such that, after those moves, there will be the same number of letters "a" and "b" on the board (or returns -1 if it is impossible).

Examples
01 · Example 1
L = "aaabab"
start = 0
return = 1
The game piece must move one field to the right. This way, the first letter of L will be switched to produce string "baabab". Both letters occur three times in this string.
02 · Example 2
L = "aaabab"
start = 6
return = 5
The game piece has to move 5 times to the left: "aaabab" → "aaaaba" → "aaabba" → "aababa" → "aabbaa" → "abbbaa" Output: 5
03 · Example 3
L = "ababa"
start = 1
return = -1
It is impossible to equalize the number of letters "a" and "b". Output: -1
04 · Example 4
L = "babbaa"
start = 2
return = 0
The number of letters "a" and "b" is already equal.
Constraints
  • N is an integer within the range [1..100].
  • L is made only of the characters 'a' and/or 'b'.
  • start is an integer within the range [0..N].
More Microsoft problems
drafts saved locally
public int balanceGameBoard(String L, int start) {
  // write your code here
}
L"aaabab"
start0
expected1
sign in to submit