SpecialStrings

SRM 634 · 2014-08-25 · by lg5293

SRM 634 · 2014-08-25 · by lg5293 · Greedy, Search, String Manipulation

Show categories

Class Name: SpecialStrings

Return Type: String

Method Name: findNext

Arg Types: (string)

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.

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"

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

Coding Area

Language: C++17 · define a public class SpecialStrings with a public method string findNext(string current) · 98 test cases · 2 s / 256 MB per case