8
\$\begingroup\$

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

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

1 Answer 1

9
\$\begingroup\$

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

\$\endgroup\$
11
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – tsh
    Jul 21 at 7:40
  • 2
    \$\begingroup\$ @cheems please bear with me, I have to fully understand it myself first! \$\endgroup\$
    – loopy walt
    Jul 21 at 9:01
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ Jul 21 at 11:48
  • 1
    \$\begingroup\$ @JonathanAllan Sure, Done. \$\endgroup\$
    – cheems
    Jul 21 at 11:53
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Jul 21 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.