Next Special String

Question

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 code-golf restricted-time restricted-complexity , 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

Answer 1

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).