NetworkXZeroOne | Topcoder Archive

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.

Definition

Class:: NetworkXZeroOne
Method:: reconstruct
Parameters:: String
Returns:: String
Method signature:: String reconstruct(String message)
(be sure your method is public)

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"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.