NetworkXZeroOne

SRM 516 · 2011-05-25 · by dolphinigle

SRM 516 · 2011-05-25 · by dolphinigle · Simple Search, Iteration

Show categories

Class Name: NetworkXZeroOne

Return Type: String

Method Name: reconstruct

Arg Types: (string)

Problem Statement

Toastman has sent Fox Ciel a message consisting entirely of lowercase 'o' and 'x' letters. This message has the interesting property that for any even-length contiguous substring of this message, the number of 'o's will equal the number of 'x's.

Unfortunately due to the nature of the network, some of the letters in the message can become corrupted. You are given a String message, each character of which is 'o', 'x', or '?'. 'o' or 'x' denotes that the letter in the message is not corrupted and is equal to the corresponding letter. A '?' denotes that the letter at that position is corrupted and might have been either 'o' or 'x'.

Your job is to replace each of the '?' characters in the input by either 'o' or 'x' such that the resulting message has the interesting property described above, and return that corrected message. It is guaranteed that there will be exactly one such message for the given input.

Constraints

message will contain between 2 and 50 characters, inclusive.
Each character in message will be lowercase 'o', lowercase 'x', or '?'.
There will be exactly one possible corrected message which has the interesting property described in the problem statement.

Examples

"x?x?"
Returns: "xoxo"

Consider the entire message, which is a contiguous substring of the input message of length 4, which is even. It has two 'x's, so it follows that the other two '?' characters must be both 'o'.

"?xo?"
Returns: "oxox"

Consider the first two characters of message. Since it's a contiguous substring of the input message and has a length of 2, which is even, and since it already contains one 'x', the first '?' must be 'o'. Then, by considering the entire message as a contiguous substring of length 4, the last character must be 'x'.

"xo"
Returns: "xo"

Sometimes the message is not corrupted.

"o??x??o"
Returns: "oxoxoxo"

"???????x"
Returns: "oxoxoxox"

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

Coding Area

Language: C++17 · define a public class NetworkXZeroOne with a public method string reconstruct(string message) · 211 test cases · 2 s / 256 MB per case