Connection Status:
Competition Arena > TaroFillingAStringDiv2

TaroFillingAStringDiv2

SRM 650 · 2015-01-29 · by Witaliy

SRM 650 · 2015-01-29 · by Witaliy · Brute Force
Class Name: TaroFillingAStringDiv2
Return Type: int
Method Name: getNumber
Arg Types: (string)
Problem Statement

Problem Statement

Cat Taro likes strings. You are given a String S. Each character of S is 'A', 'B', or '?'.

To Taro, the ugliness of a string is the number of pairs of equal consecutive characters. For example, the ugliness of "ABABAABBB" is 3: there is one pair "AA" and two (overlapping) pairs "BB".

Taro now wants to change each question mark in S either to 'A' or to 'B'. His goal is to minimize the ugliness of the resulting string. Return the smallest ugliness that can be achieved.

Constraints

  • S will contain between 1 and 50 characters, inclusive.
  • S will consist only of characters 'A', 'B' and '?'.
Examples
0)
"ABAA"
Returns: 1

There is initially one pair of consecutive digits that are equal in this case. There is no characters that Taro has to replace, hence the answer is 1.

1)
"??"
Returns: 0
2)
"A?A"
Returns: 0
3)
"A??B???AAB?A???A"
Returns: 3
4)
"?BB?BAAB???BAB?B?AAAA?ABBA????A?AAB?BBA?A?"
Returns: 10

Submissions are judged against all 87 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TaroFillingAStringDiv2 with a public method int getNumber(string S) · 87 test cases · 2 s / 256 MB per case

Submitting as anonymous