Dada una cadena como entrada, encuentre la subcadena contigua más larga que no tenga ningún carácter dos veces o más. Si hay varias de estas subcadenas, también puede generarlas. Puede suponer que la entrada está en el rango ASCII imprimible si lo desea.

Tanteo

Las respuestas se clasificarán primero por la longitud de su propia subcadena no repetida más larga, y luego por su longitud total. Los puntajes más bajos serán mejores para ambos criterios. Dependiendo del idioma, esto probablemente se sentirá como un desafío de código de golf con una restricción de fuente.

Trivialidad

En algunos idiomas, lograr un puntaje de 1, x (lenguaje) o 2, x (Brain-flak y otras lonas de turing) es bastante fácil, sin embargo, hay otros idiomas en los que minimizar el subsuelo más largo que no se repite es un desafío. Me divertí mucho obteniendo un puntaje de 2 en Haskell, así que te animo a buscar idiomas donde esta tarea sea divertida.

Casos de prueba

"Good morning, Green orb!" -> "ing, Gre"
"fffffffffff" -> "f"
"oiiiiioiiii" -> "io", "oi"
"1234567890"  -> "1234567890"
"11122324455" -> "324"

Presentación de puntaje

Puede calificar sus programas con el siguiente fragmento:

input.addEventListener("input", change);

// note: intentionally verbose :)
function isUnique(str) {
  var maxCount = 0;
  var counts = {};
  for(var i = 0; i < str.length; i++) {
    var c = str.charAt(i);
    counts[c] |= 0;
    counts[c]++;
    if(maxCount < counts[c]) {
      maxCount = counts[c];
    }
  }
  return maxCount <= 1;
}

function maximizeSubstring(str, pred, cost) {
  var mostExpensive = -1;
  // iterate over substrings
  function iterate(start, end) {
    var slice = str.slice(start, end);
    if(pred(slice)) {
      var profit = cost(slice);
      if(profit > mostExpensive) {
        mostExpensive = profit;
      }
    }
    end++;
    if(start >= str.length) {
      return;
    }
    else if(end > str.length) {
      start++;
      iterate(start, start);
    }
    else {
      iterate(start, end);
    }
  }
  iterate(0, 0);
  return mostExpensive;
}

function size(x) {
  return x.length;
}

function longestNonRepeatingSize(str) {
  return maximizeSubstring(str, isUnique, size);
}

function change() {
  var code = input.value;
  output.value = "Your score is: " + longestNonRepeatingSize(code);
}

change();

* {
  font-family: monospace;
}

Input code here:
<br>
<textarea id="input"></textarea>
<br>
<textarea id="output"></textarea>

C, puntuación de 2,  747   720  662 bytes

L  [  1  <<  7  ]  ,  *  q  ,  *  r  ,  l  ,  d  ,  i  ,  c  ,  j  ,  s  ,  t  ,  k  =  1  <<  7  ;  h  (  )  {  q  =  s  +  i  +  j  ++  ;  *  q  %  k  &&  !  L  [  *  q  %  k  ]  ++  &&  h  (  ++  c  )  ;  }  g  (  )  {  q  =  s  +  i  ;  *  q  %  k  ?  z  (  k  )  ,  h  (  j  =  c  =  0  )  ,  c  >  d  &&  (  d  =  c  )  &&  (  l  =  i  )  ,  g  (  ++  i  )  :  0  ;  }  f  (  S  ,  T  )  {  s  =  S  ;  l  =  i  =  d  =  0  ;  g  (  t  =  T  )  ;  p  (  i  =  0  )  ;  }  p  (  )  {  q  =  s  +  l  +  i  ;  r  =  t  +  i  ;  i  ++  <  d  ?  p  (  *  r  =  *  q  )  :  (  *  r  =  0  )  ;  }  z  (  i  )  {  L  [  --  i  ]  =  0  ;  i  &&  z  (  i  )  ;  }

Funciona al menos en MinGW de 32 bits (con optimizaciones deshabilitadas). No usa una sola palabra clave.

Al parecer, también funciona en TIO con gcc y clang: ¡ Pruébelo en línea! (¡Gracias @ Dennis!)

Llamar con:

int main()
{
    char str[1024];

    f("Good morning, Green orb!", str);
    puts(str);

    f("fffffffffff", str);
    puts(str);

    f("oiiiiioiiii", str);
    puts(str);

    f("1234567890", str);
    puts(str);

    f("L  [  1  <<  7  ]  ,  *  q  ,  *  r  ,  l  ,  d  ,  i  ,  c  ,  j  ,  s  ,  t  ,  k  =  1  <<  7  ;  h  (  )  {  q  =  s  +  i  +  j  ++  ;  *  q  %  k  &&  !  L  [  *  q  %  k  ]  ++  &&  h  (  ++  c  )  ;  }  g  (  )  {  q  =  s  +  i  ;  *  q  %  k  ?  z  (  k  )  ,  h  (  j  =  c  =  0  )  ,  c  >  d  &&  (  d  =  c  )  &&  (  l  =  i  )  ,  g  (  ++  i  )  :  0  ;  }  f  (  S  ,  T  )  {  s  =  S  ;  l  =  i  =  d  =  0  ;  g  (  t  =  T  )  ;  p  (  i  =  0  )  ;  }  p  (  )  {  q  =  s  +  l  +  i  ;  r  =  t  +  i  ;  i  ++  <  d  ?  p  (  *  r  =  *  q  )  :  (  *  r  =  0  )  ;  }  z  (  i  )  {  L  [  --  i  ]  =  0  ;  i  &&  z  (  i  )  ;  }");
    puts(str);
}

Salida:

El código con un formato ligeramente más legible:

L[1<<7],
*q, *r, l, d, i, c, j, s, t, k=1<<7;

h()
{
    q = s+i+j++;
    *q%k && !L[*q%k]++ && h(++c);
}

g()
{
    q = s+i;
    *q%k ? z(k), h(j=c=0), c>d && (d=c) && (l=i), g(++i) : 0;
}

f(S, T)
{
    s = S;
    l = i = d = 0;
    g(t=T);
    p(i=0);
}

p()
{
    q = s+l+i;
    r = t+i;
    i++<d ? p(*r=*q) : (*r=0);
}

z(i)
{
    L[--i] = 0;
    i && z(i);
}

Y esto se puede usar para generar el espaciado adecuado para llegar al formato con puntaje 2: ¡ Pruébelo en línea!

C, puntaje 3, 309 bytes

i
,
j
,
l
,
c
,
d
;
f
(
\
c\
\
h\
\
a\
\
r
*
s
)
{
\
f\
\
o\
\
r
\
(
i
=
l
=
d
=
0
;
s
[
i
]
;
c
>
d
&&
(
d
=
c
)
&&
(
l
=
i
)
,
++
i
)
\
f\
\
o\
\
r
(
\
c\
\
h\
\
a\
\
r

L
[
\
1\
\
2\
\
8
\
]
=
{
j
=
c
=
0
}
;
s
[
i
+
j
]
&&
!
L
[
s
[
i
+
j
++
]
]
++
;
++
c
)
;
\
w\
\
r\
\
i\
\
t\
\
e
(
1
,
s
+
l
,
d
)
;
}

Pruébalo en línea!

Haskell , puntaje 2, 492 ... 307 224 212 209 207 bytes

((yy:yyy))??ss|ss==yy  =  ""  |  yy==yy=yy:yyy??ss
ss??sss=ss
ss""=""

ss((ff:fff))  =  ff  :  ss  fff??ff
ff""=""

ff((xxx:xx))  =  ss((xxx:xx))##ff  xx
xx##xxx  |  ((((xx>>xx))<))  $  xxx>>xx=xxx|xx==xx=xx

Pruébalo en línea!

¡Golfó literalmente cientos de bytes gracias a WW y Ørjan Johansen !

Explicación

La función (??)toma un carácter cy una cadena sy devuelve el prefijo más largo sque no contiene c. Sin golf y no optimizado para la puntuación:

c ?? (y:s)  
    | c==y = ""
    | True = y : c ?? s
c ?? s = s

La función ssutiliza (??)para encontrar el prefijo más largo de caracteres únicos de una cadena dada:

ss (x:r) = x : (x ?? ss r)
ss "" = ""

(##)es una función que toma dos cadenas y devuelve la más larga. La comparación de longitud funciona repitiendo la cadena xtantas veces como xsea ​​largo ( x>>y) y como yes largo ( y>>x) y verificando cuál de las cadenas resultantes es lexicográficamente más grande.

x ## y
  | (x>>x) < (y>>x) = y
  | True = x

Finalmente se ffrepite sobre la cadena de entrada, genera el prefijo más largo con ss, determina recursivamente la subcadena no repetida más larga de la cola de la cadena y devuelve la más larga de las dos con (##):

ff "" = ""
ff (x:r) = ss(x:r) ## ff r

Lua, puntaje 3, 274 bytes

g='g'..'s'..'u'..'b'  _G  [  'l'..'o'..'a'..'d'  ](  g[g  ](  "s  =...f  o  r d = # s - 1 , 0 , - 1 d  o f  or r = 1 , # s - d d  o t = s :s  ub  (r  ,r  +d  )i  f n  ot t:  fi  nd  '(  .)  .*  %1  't  he  n p  ri  nt  (t  )r  et  ur  n en  d e  n  d e  nd  ","  ",""))(...)

Nota: se requiere Lua 5.2 o Lua 5.3

Uso:

$ lua lnrs.lua "Good morning, Green orb!"
ing, Gre
$ lua lnrs.lua "fffffffffff"
f
$ lua lnrs.lua "oiiiiioiiii"
oi
$ lua lnrs.lua "1234567890"
1234567890
$ lua lnrs.lua "11122324455"
324

Idea principal: intercalar todo con espacios, insertar " "(dos espacios) para dividir identificadores largos

Código sin golf:

g = "gsub"
_G["load"](
   g[g](      -- g[g] == string.gsub - a function for substitution of substrings
      "The source of actual program, but two-space sequences were inserted in some places", 
      "  ",   -- we are replacing all two-space substrings
      ""      -- with an empty string
   )
)(...)

Programa real (después de eliminar todos los pares de espacios):

s = ...
for d = #s - 1, 0, -1 do
   for r = 1, #s - d do
      t = s:sub(r, r+d)
      if not t:find"(.).*%1" then
         print(t)
         return
      end
   end
end

Por cierto, el fragmento JS para calcular la puntuación falla en mi código.

Retina 0.8.2 , 37 bytes, puntaje 9

.
$&$'¶
(.)(?<=\1.+).*

O#$^`
$.&
1G`

Pruébalo en línea! La traducción directa de esta respuesta a Retina 1 guarda un byte usando en Nlugar de O#. Sin embargo, si ingenuamente juega golf, la Retina 1 responde a 28 bytes, ¡su puntuación en realidad aumenta a 10! Explicación:

.
$&$'¶

Genere todos los sufijos de la entrada.

(.)(?<=\1.+).*

Para cada sufijo, tome el prefijo hasta el primer carácter duplicado.

O#$^`
$.&

Ordene las cadenas restantes en orden inverso de longitud (es decir, las más largas primero).

1G`

Toma el más largo.

Jelly , puntaje 2, 14 bytes

Ẇµµff  Q  €  Ṫ

Gracias a @JonathanAllan por el puntaje -1, +7 bytes y por notar un error.

Pruébalo en línea!

Cómo funciona

Ẇµµff  Q  €  Ṫ  Main link. Argument: s (string)

Ẇ               Window; yield all substrings of s, sorted by length.
 µ              Begin a new chain. Argument: A (array of substrings)
  µ             Begin a new chain. Argument: A (array of substrings)
   f            Filter A by presence in itself. Does nothing.
       Q  €     Unique each; deduplicate all strings in A.
    f           Filter A by presence in the array of deduplicated substrings,
                keeping only substrings composed of unique characters.
             Ṫ  Tail; take the last (longest) kept substring.

Limpio , puntaje 7 5, 276 bytes

@[ss:s]=rr(pp[][ss:s])((@s))
@s=s
ee x[rr:xx]|e x rr=True=ee x xx
ee x xx=f
f=e'e'' '
e::!  Char  !  Char  ->Bool
e  _ _=  code  {

eqC
}
pp p[r:rr]|ee r p=p=pp(a r p)rr
pp a _=a
a  x[ll:l]=[ll:a x  l]
a l ll=[l]
l[]rr=e'l''l'
l ff[]=f

l[r:rr][ss:ll]=l rr ll
rr x y|l x y=y=x

Pruébalo en línea! Gracias a @ Οurous por mostrarme que es posible llamar al código de máquina ABC directamente desde Clean. Esto permite deshacerse del cuello de botella anterior importque establece el puntaje mínimo en 7, pero necesita la palabra clave codeque establece el puntaje mínimo en 5 para este enfoque.

Aquí puede encontrar una versión no optimizada y sin puntaje optimizado del código anterior: ¡ Pruébelo en línea!

Versión anterior con puntaje 7, 158 154 130 bytes

import  StdEnv  
@[xx:rr]=c(%[][xx:rr])(@rr)
@e=e
c s b|  length  s<  length  b=b=s
%s[xx:r]|  isMember xx s=s= %(s++[xx])r
%r _=r

Pruébalo en línea!

Con la importpuntuación no puede ir por debajo de 7. Sin la importación, sería necesario implementar la igualdad en cadenas o caracteres sin ninguna función de biblioteca que probablemente no sea ​​posible, como se puede ver en la nueva versión anterior.

Python 3 , puntaje 4, 155 bytes

exec(('l=la''mbd''a f'',e=en''ume''rat''e:m''ax''([f[ j  :k]  for  j,i in e ( f)f''or  k,i in e ( f )if  len  ( { *''f[j'':k]''})==k-''j],''key''=le''n)'))

Esto define una función l.

Gracias a @xnor por señalar que las cadenas de longitud 3 no aumentan la puntuación, ahorrando 32 bytes.

Pruébalo en línea!

Brachylog , puntaje 2, 19 bytes

s  ᶠ  l  ᵒ  ≠  ˢ  t

Pruébalo en línea!

Solo una vieja y aburrida respuesta de "espacia todo". Al menos aprendí que los metapredicados se pueden separar de los predicados y aún funcionan (y los subíndices y superíndices (paramétricos) no pueden).

s ᶠ - encuentra todas las subcadenas de la cadena dada

l ᵒ - ordenarlos por su longitud (ascendente por defecto)

≠ ˢ - seleccione aquellos que tienen todos los elementos distintos

t - obtener la cola (último elemento) de eso - el que tiene la mayor longitud

Pyth , 11 bytes, puntaje 4

-4 puntuación gracias a Dennis

e lD {I# .:

elD{I#.:Q      Full program, inputs "string" from stdin and outputs to stdout
e              The last element of the list generated by taking
      .:Q      All substrings of the input
     #         Filtered for
   {I          Being invariant over deduplicate i.e. being "non-repeating"
 lD            and sorted by length

Pruébalo en línea!

Cáscara , puntaje 2, 10 bytes

►IIËII≠IIQ

Pruébalo en línea!

Explicación

El programa es equivalente a esto:

►Ë≠Q  Implicit input.
   Q  List of substrings.
►     Find one that maximizes:
 Ë    all ordered pairs
  ≠   are inequal.

El incorporado Ëevalúa ≠en todos los pares ordenados de su argumento x, y devuelve length(x)+1si cada resultado es verdadero, de lo contrario 0. Cuando maximizamos esto, encontramos la cadena más larga que no tiene caracteres repetidos.

En el envío, simplemente inserto la función de identidad Ientre cada función, dos veces. Como IËes lo mismo que Ë, I≠es lo mismo ≠y así sucesivamente, esto no cambia la semántica. El único peligro es que una función de orden superior podría decidir usar uno de los Is como argumento, pero afortunadamente eso lleva a un error de tipo en nuestro programa, por lo que no sucede.

Clojure, puntaje 4

#(  let  [N  (fn  [[_ & r]] r) R  (fn  R [f v c]  (if  c (R f (f v (  nth  c 0))  ( N  c)) v)) C  (fn  C  (  [i]  (C (  seq  i) 0)) ( [i  n]  (if i (C ( N  i )  (  inc n)) n)))  J  (fn  [c  i]  (assoc c (C  c) i)) I  (fn  F [f i n R]  (if ( =  (C  R) n) R (F f (f  i) n ( J  R (f  i)))))] ( apply  str  (R ( fn  [a  b] ( if  (< (C  a)  (C  b)) b a )) "" (  for  [k  (I N % (C  % ) [])]  (R  ( fn [ t  c ] ( if ( or ( = t (  str t) ) ((  set t)c))(apply  str t) ( J  t c)))[]k)))))

¡Oh hombre, esto fue doloroso! Nimplementa next, Res reduce, Ces count, Jes conj(funciona solo para vectores) y Ies iterate. apply strEs allí dos veces porque de lo contrario "aaaa" de entrada no volvería una cadena, sino un vector [\a]. Afortunadamente, pude usar applyy assocno sabía que podía asociar un índice más allá del último elemento de un vector: o

Jalea , puntaje 5, 10 bytes

ẆµQQ⁼µÐfµṪ

Pruébalo en línea!

Python 3 , puntaje 4, 317 bytes

exec(('%s'  *58  %(  's=','in','pu','t(',');','pr','in','t(','so','rt','ed','((s','[i',':j',']f','or',' j',' i','n ','ra','ng','e(','1,','le','n(','s)','+1',')f','or',' i',' i','n ','ra','ng','e(','j)','if',' l','en','(s','et','(s','[i',':j',']))','==l','en','(s','[i',':j',']))',',k','ey','=l','en',')[','-1','])')))

Pruébalo en línea!

Código no eliminado:

s=input();print(sorted((s[i:j]for j in range(1,len(s)+1)for i in range(j)if len(set(s[i:j]))==len(s[i:j])),key=len)[-1])

lambda acontiene el mbda que tiene puntaje 5, y necesita una función returnque aparentemente no se puede execeditar (por lo tanto, toma un puntaje de al menos 5 para eturn), por lo que fue necesario un programa completo. Probablemente sea posible reducir un poco el tamaño del código no ejecutado, pero no puedo ver una mejora clara y rápida.

Alice , 40 bytes

/ii..nn$$@@BBww..DD~~FF..!!nn$$KK??oo@@

(Nueva línea final)

Pruébalo en línea!

El puntero de instrucciones se mueve diagonalmente en modo ordinal, por lo que solo se ejecuta cualquier otro carácter.

[email protected]~F.!n$K?o@

i     take input
.n$@  terminate if empty
B     push all nonempty substrings, with the longest on the top of the stack
w     push return address (start main loop)
.     make copy of current substring
D     deduplicate characters
~     swap: this places the original above the deduplicated copy
F     Push the original string if it is a substring of the deduplicated copy
      (which can only happen if they're equal); otherwise push empty string
.!    place a copy on the tape
n$K   if the empty string was pushed, return to start of loop
o     output
@     terminate

Perl 6 , puntaje: 15 10 8, longitud: 46 55 62 bytes

{~m:ov/(.+)<!{$0.comb.repeated}>/.max(&chars)}

Pruébalo

{~m:ov/(..*)<!{(($0)).comb.repeated}>{{}}/.max(&chars)}

Pruébalo

{m:ov:i/(..*)<!{(($0)).comb.repeated}>{{}}/.max((&chars)).Str}

Pruébalo

Expandido:

{    # bare block lambda with implicit parameter ｢$_｣

    m                          # match (implicitly against ｢$_｣)
    :overlap                   # in every single way possible
    :ignorecase                # add a ｢:｣ to break up substring
    /

      (..*)                    # match at least one character

      <!{
        (($0)).comb.repeated  # backtrack if there were repeats
      }>

      {{}}                    # anon hash in code block (no-op)
    /

    .max((&chars))            # get the longest

    .Str                      # coerce to a Str (from a Match object)
}

Java 8, puntaje 9 (384 B) 7 (401 B)

S -> { int s = 0 , e = 0 , l = 0 , x = 0 , y = 0 , b [ ] = new int [ 256 ] ; for ( ; x <S.  length  & y <S.  length  & l <S.  length  - x ; x ++ ) { b [S[x]] = 1 ; for ( y ++ ; y <S.  length  && b [S[y]] < 1 ; b [S[y ++]] = 1 ) ; if ( l < y - x ) { s = x ; e = y ; l = y - x ; } for ( ; y <S.  length  && x < y & S[x] != S[y  ];)b [S[x ++]] = 0 ; }  String g=""; for( ; s<e ; g+= S[s++]);  return  g;}

• Versión inicial. Bajaré desde aquí. El puntaje es de 9 "ubstring ", por substringlo que será la primera parte para reemplazar.
• El puntaje ahora es 7 debido a " length", lo que probablemente no pueda reducir aún más. Dudo que sea posible eliminar los cuatro usos de length. Si es posible, " eturn"(6) podría reducir la puntuación en 1 como mejora final, pero supongo que esto es todo (excepto tal vez una pequeña reducción en el conteo de bytes ...)

Pruébalo en línea.

Haskell , puntaje 7

-4 gracias a Laikoni.

import  Data.List  
f s=snd $ maximum [ (0<$i ,i)|i<-  tails  =<<inits s, nub i==i]

Pruébalo en línea!

Mathematica, puntaje 11 9

Length@Last@Select[Subsequences[Characters@#],#==DeleteDuplicates  @#&]&

Afeitando un par de bytes de la cadena no repetitiva más larga al ocultar el nombre de la función:

Length@Last@Select[Subsequences[Characters  @#],#==(  ToExpression@ 
StringJoin@@FromCharacterCode@{{68},{101},{108},{101},{116},{101},{68},{117},
{112},{108},{105},{99},{97},{116},{101},{115}}))@#&]&

Kotlin , puntuación: 11 10 9 bytes, longitud: 227 246 245 bytes

indices
  .flatMap { p -> indices . map { p to p + it } }
  .  filter { (r,i) -> i < length  }
  .map { ( s , a )->substring  (  s,  a  ) }
  .  filter { it  .  groupBy  { it } .  none { ( k , v )->v . size>1 } }
  .maxBy { it.length }

El más largo es ubstring, que son 9 caracteres.

Se llama así:

val c = "Good morning, Green orb!"

fun String.c(): String? = indices
    .flatMap { p -> indices . map { p to p + it } }
    .  filter { (r,i) -> i < length  }
    .map { ( s , a )->substring  (  s,  a  ) }
    .  filter { it  .  groupBy  { it } .  none { ( k , v )->v . size>1 } }
    .maxBy { it.length }

fun main(args: Array<String>) {
    val text = """indices
    .flatMap { p -> indices . map { p to p + it } }
    .  filter { (r,i) -> i < length  }
    .map { ( s , a )->substring  (  s,  a  ) }
    .  filter { it  .  groupBy  { it } .  none { ( k , v )->v . size>1 } }
    .maxBy { it.length }"""
    val message = text.c()!!
    println(message)
    println(text.length)
    println(message.length)
    println(c.c())
}

Pyth , puntaje 3 (  18  14 bytes)

e  fq  T{T  .:

Pruébalo en línea!

La subcadena más larga que no se repite es  .:.

05AB1E , 22 bytes | Puntuación: 2

Œ  ʒ  D  Ù  Q  }  é  ¤

-1 puntuación + 7 bytes gracias a HeebyJeeby

Pruébalo en línea!

05AB1E , 15 bytes | Puntuación: 3

Œ ʒ D Ù Q } é ¤

Pruébalo en línea!

05AB1E , 8 bytes | Puntuación: 8

ŒʒDÙQ}é¤

Pruébalo en línea!

05AB1E realmente puede hacer algo bastante barato ... agregar espacios en blanco en 05AB1E no hace nada.

Si hay una regla en contra de esto, también puedo usar ´y gustar otros 7 caracteres.