0votos

Longitud de la substring con los caracteres dados en JavaScript

por josejuan hace 6 años

El coste es exactamente |C| + 2 * |S| iteraciones. El coste de preparar el diccionario de elementos a buscar |C| y el coste de iterar una única vez dos índices la secuencia |S|. El algoritmo funciona para secuencias |S|, por lo que puede ser arbitrariamente larga sin afectar al rendimiento práctico (ej. lectura de archivos muy grandes).

Dada una String s y unos caracteres desarrollar el código que determine la longitud de la substring más corta de s que contenga todos los caracteres dados.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/* 
 
  La estrategia general es: 
 
    a b r a c a d a b r a 
        i       j 
 
    1. aumentamos 'j' hasta que estén todas 
    2. aumentamos 'i' hasta que no lo estén 
 
  Intercalando [1] y [2] enumeraremos todas las 
  subcadenas que cumplen la condición, así, basta 
  mirar cual de ellas tiene longitud mínima (haciendo 
  sólo una resta de índices). 
 
*/ 
 
/* 
  Funciona para conjuntos (arrays) no sólo cadenas. 
  Ej. 
 
      minSubSet( 
        "OLE".split(''), 
        "ELRAPIDOLINCESECOMIOALRATON".split('') 
      ).join(''); 
 
  devuelve 
 
      "OLINCE" 
 
*/ 
function minSubSet(C, S) { 
 
  // intervalo Sij 
  var i = 0, j; 
 
  // mejor solución 
  var _i = -1, _j = S.length + 1; // en lugar de S.length puede hacer +inf 
 
  // nº diferente de elementos de C que están en el intervalo Sij 
  var nd = 0; 
 
  // nº de elementos de C 
  var ne = 0; 
 
  // nº de elementos de cada C que están en el intervalo Sij 
  var nc = {}; 
 
  // preparación de C con coste O(|C|) 
  C.forEach(function (k) { 
    nc[k] = 0; 
    ne += 1; 
  }); 
 
  // buscamos primer elemento de C en S 
  while(i < S.length) { // puede cambiarse por EOF 
    if(nc[S[i]] === 0) 
      break; 
    i++; 
 
  for(j = i; j < S.length; j++) { // puede cambiarse por EOF 
 
    // si es un elemento de C 
    if(nc[S[j]] != undefined) { 
 
      nc[S[j]] += 1; 
 
      // el elemento no estaba aún en el intervalo Sij 
      if(nc[S[j]] == 1) { 
 
        nd++; 
 
        // si están todos los elementos 
        if(nd == ne) { 
 
          // es posible que podamos acortar por la izquierda 
          while(i <= j && (nc[S[i]] == undefined || nc[S[i]] > 1)) { 
            if(nc[S[i]] != undefined) 
              nc[S[i]] -= 1; 
            i += 1; 
 
          // esta cadena es candidata a ser la mejor 
          if(_j - _i > j - i) {_j = j; _i = i;} 
 
          // ahora quitamos el de la izquierda (que es mínimo necesario) 
          nc[S[i]] = 0; 
          i += 1; 
          nd--; 
 
 
 
 
 
  // sin solución 
  if(_i < 0) 
    return []; 
 
  return S.slice(_i, _j + 1); 
 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.