Escribí una función que toma una matriz de palabras y devuelve un objeto con la letra y la longitud de la subcadena más larga de esa letra.
Pregunta:
Dadas las
words = ["aabb", "aaaa", "bbab"], su función debería devolver6y"a".
Una de las mejores concatenaciones eswords[1] + words[0] + words[2] = "aaaaaabbbbab".Salida:
{ "letter": "a", "length": 6 }
Mi problema es que con esta función estoy devolviendo:
{ "letter": "a", "length": 4 } const longestSubstring = (value) => { const stringArray = value.join("").split(""); let i = 0; let longest = { letter: "", length: 0, }; let current = { letter: "", length: 0, }; while (i < stringArray.length) { letter = stringArray[i]; if (current.letter != letter) { current = { letter, length: 0, }; } current.length += 1; if (current.length > longest.length) { longest = { ...current }; } i += 1; } return longest; }; console.log(longestSubstring(["aabb", "aaaa", "bbab"]))Aquí hay un enfoque de fuerza bruta similar a la respuesta existente de IT Goldman , pero más corto:
function *permute(a, i=0) { if (i >= a.length) { yield a.slice(); } for (let j = i; j < a.length; j++) { [a[i], a[j]] = [a[j], a[i]]; yield *permute(a, i + 1); [a[i], a[j]] = [a[j], a[i]]; } } const splitRuns = s => s.match(/(.)\1*/g); const longestRun = s => splitRuns(s).reduce((a, e) => e.length > a.length ? e : a, "") ; const longestSubstring = a => [...permute(a)] .map(e => e.join("")) .reduce((a, e) => { const candidate = longestRun(e); return a.length > candidate.length ? a : { character: candidate[0], length: candidate.length }; }, {character: null, length: 0}) ; console.log(longestSubstring(["aabb", "aaaa", "bbab"])); console.log(longestSubstring(["xxbxx", "xbx", "x"])); console.log(longestSubstring(["dd", "bb", "cc", "dd"])); La función de permutación es una rutina de biblioteca genérica y lista para usar (y es responsable de la terrible complejidad exponencial de tiempo y espacio), por lo que el resto de la tarea consiste en unir cada permutación en una sola cadena, detectando ejecuciones continuas de caracteres repetidos con la expresión regular s.match(/(.)\1*/g) y encontrar la secuencia más larga de estos caracteres repetidos.
{character: "a", length: 6} es un resultado un tanto tonto, sin embargo, las cadenas ya tienen una longitud, por lo que también podría devolver la cadena en lugar de un objeto. También llamaría a la función longestPermutedConcatenatedRun o algo así, porque longestSubstring más larga hace que suene como un algoritmo de cadena simple. Eso es, sin embargo.
Es un problema interesante y todavía no tengo claro cómo optimizarlo aún más.
Relacionado:
Todos sabemos cómo obtener todas las permutaciones de una matriz (ver otras preguntas en SO). Así que usemos eso y la fuerza bruta a nuestra manera. Además, necesitamos una función para contar la racha de letras en una matriz/cadena.
const permutator = (inputArr) => { let result = []; const permute = (arr, m = []) => { if (arr.length === 0) { result.push(m) } else { for (let i = 0; i < arr.length; i++) { let curr = arr.slice(); let next = curr.splice(i, 1); permute(curr.slice(), m.concat(next)) } } } permute(inputArr) return result; } function longesLetterStreak(arr) { var arr = arr.join("").split("") var last = null; var streak = 0; var result = { letter: null, count: 0 }; for (var i = 0; i < arr.length; i++) { var letter = arr[i]; if (letter != last) { if (streak > result.count) { result = { letter: last, count: streak } streak = 1; } } else { streak++; } last = letter; } if (streak > result.count) { result = { letter: last, count: streak } } return result } const longestSubstring = (value) => { var result = { letter: null, count: 0 }; var possibilites = permutator(value); possibilites.forEach(function(possibility) { var sofar = longesLetterStreak(possibility); if (sofar.count > result.count) { result = sofar; } }) return result; }; console.log(longestSubstring(["aabb", "aaaa", "bbab"]))