SpecialStrings | Topcoder Archive

Problem Statement

A string S is called special if it satisfies the following two properties:

Each character in S is either '0' or '1'.
Whenever S = UV where both U and V are nonempty strings, U is strictly smaller than V in lexicographic order.

For example, the string S = "00101" is special because we have "0" < "0101", "00" < "101", "001" < "01", and "0010" < "1".

You are given a String current that is guaranteed to be special. Let N be the length of current. Consider the lexicographically sorted list of all special strings of length N. Compute and return the string that comes immediatelly after current in this list. If current happens to be the last string in the list, return an empty String instead.

Definition

Class:: SpecialStrings
Method:: findNext
Parameters:: String
Returns:: String
Method signature:: String findNext(String current)
(be sure your method is public)

Notes

Given two different strings U and V, the string U precedes the string V in lexicographic order if one of two conditions is satisfied: Either U is a proper prefix of V, or there is an integer x such that U and V have the same first x characters, and the x+1th character in U is smaller than the x+1th character in V.

Constraints

current will contain between 1 and 50 characters, inclusive.
current will be a special string.

Examples

```
"01"
```
```
Returns: ""
```
"01" is the only special string of length 2.
```
"00101"
```
```
Returns: "00111"
```
The special strings of length 5 are "00001", "00011", "00101", "00111", "01011", "01111".
```
"0010111"
```
```
Returns: "0011011"
```

"000010001001011"

Returns: "000010001001101"

"01101111011110111"

Returns: "01101111011111111"

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.