Problem Brief

Balance the Game Board

FULLTIMEOA

See Microsoft online assessment and 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).

1Example 1

Input

L = "aaabab", start = 0

Output

Explanation

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.

2Example 2

Input

L = "aaabab", start = 6

Output

Explanation

The game piece has to move 5 times to the left: "aaabab" → "aaaaba" → "aaabba" → "aababa" → "aabbaa" → "abbbaa" Output: 5

3Example 3

Input

L = "ababa", start = 1

Output

-1

Explanation

It is impossible to equalize the number of letters "a" and "b". Output: -1

4Example 4

Input

L = "babbaa", start = 2

Output

Explanation

The number of letters "a" and "b" is already equal.

Constraints

Limits and guarantees your solution can rely on.

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].