I have written a function that takes an array of words and returns an object with the letter and the length of the longest substring of that letter
Question:
Given the
words = ["aabb", "aaaa", "bbab"], your function should return6and"a".
One of the best concatenations iswords[1] + words[0] + words[2] = "aaaaaabbbbab".Output:
{ "letter": "a", "length": 6 }
My issue is that with this function I am returning:
{ "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"]))Here's a similar brute force approach to the existing answer from IT goldman, but shorter:
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"]));The permutation function is a generic, off-the-shelf library routine (and is responsible for the terrible exponential time and space complexity), so the rest of the task is a matter of joining each permutation into a single string, detecting continuous runs of repeated characters with the regex s.match(/(.)\1*/g) and finding the longest run of these repeated characters.
{character: "a", length: 6} is somewhat silly output, though--strings already have a length, so you might as well just return the string rather than an object. I'd also call the function longestPermutedConcatenatedRun or something like that, because longestSubstring makes it sound like a simple string algorithm. Such it is, though.
It's an interesting problem and it's not clear to me how to go about optimizing this further just yet.
Related:
We all know how to get all permutations of an array (see other questions in SO). So let's use that and brute force our way. In addition we need a function to count streak of letters in an array / string.
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"]))