# Special String

We call a binary string $$\S\$$ of length $$\N\$$ special if :

• substring $$\S[0:i+1]\$$ is lexicographically strictly smaller than substring $$\S[i+1:N]\$$ for $$\ 0\leq i\leq N-2\$$,

Note: $$\ S[a:b] \$$ is substring $$\S[a]S[a+1]...S[b-1]\$$

Given a binary string $$\T\$$ of length $$\N\$$ we are interested in the first special binary string of length $$\N\$$ that is lexicographically greater than $$\T\$$, if it doesn't exist print any consistent output.

assume : $$\ 2\leq N \leq 300\$$ (just to make it even more interesting)

Examples :

• $$\T\$$= $$\0101110000\$$ the next lexicographic special string is $$\0101110111\$$
• $$\T\$$= $$\001011\$$ the next lexicographic secial string is $$\001101\$$
• $$\T\$$= $$\011\$$ the next lexicographic special string doesn't exist print $$\-1\$$ (can print any consistent value)
• $$\T\$$= $$\001101110111111\$$ the next lexicographic special string is $$\001101111001111\$$
• $$\T\$$= $$\010000000000000\$$ the next lexicographic special string is $$\010101010101011\$$
• $$\T\$$= $$\01011111111111111111111111\$$ the next lexicographic special string is $$\01101101101101101101101111\$$

This is , so the shortest answer in bytes per language that can execute in restricted $$\ O(n^4)\$$ time complexity (here $$\n\$$ is the length of string) wins.

Copyable Test case :

  0101110000 -> 0101110111

001011 -> 001101

011 -> -1(can print any consistent value)

001101110111111 -> 001101111001111

010000000000000 -> 010101010101011

01011111111111111111111111 -> 01101101101101101101101111



Sandbox

• In the Examples, wherever you say 'the next lexicographic string is...' you mean 'the next lexicographic special string is...', right? Jul 21 at 4:54
• @DominicvanEssen Yes :) edited. Jul 21 at 7:30
• Could you explain the substring notation? I don't think it's standard. Jul 21 at 8:38
• It's python notation of list slice, the right bound is excluded. Jul 21 at 8:39

# Python, 91 bytes (@tsh)

f=lambda s,j=0:f(max(s,f"{int(s[:j]+s[:-j]or s,2)+1:0{len(s)}b}"),j+1)if s[j:]else(s<"1")*s

Attempt This Online!

### Previous Python, 98 bytes

f=lambda s,j=0:f(f"{max(t:=int(s,2),t&-1<<n-j|(t>>j)+1):0{n}b}",j+1)if((n:=len(s))>j)else(s<"1")*s

Attempt This Online!

Returns empty string for failure.

### How?

The basic idea is to fix all the requirements from left to right: If s[:i]>=s[i:] increase s[i:] just enough to make it the larger operand. If i<n/2 we just need to replace the first i digits of s[i:] with those of s (and fill with zeros to the end). If i>=n/2 we need to replace s[i:] with the first n-i digits of s and add 1.

However, to streamline the logic we do the second branch all the time. This should be ok if we knew that another correction will happen before or at position 2i. But if nothing happens before 2i then at 2i we have essentially the same comparison as we had at i (at least for the i most significant bits).

• I cannot understand why it works (or does it work). I understand that it is O(n^2). And maybe 91 bytes: f=lambda s,j=0:f(max(s,f"{int(s[:j]+s[:-j]or s,2)+1:0{len(s)}b}"),j+1)if s[j:]else(s<"1")*s
– tsh
Jul 21 at 7:40
• @cheems please bear with me, I have to fully understand it myself first! Jul 21 at 9:01
• The 91 byter returns '0' for failure (I think) which becomes ambiguous for the edge-case of the input '1'. I think this should be OK, it would be if @cheems restricts the input to $N>1$ - what do you think @cheems? Jul 21 at 11:48
• @JonathanAllan Sure, Done. Jul 21 at 11:53
• I was just coming here to say that I was wrong about this output, but I think the restriction allowing that behaviour is nice as it may allow some golfs for people when they come to implement something. Jul 21 at 12:27