Concatenate array and returning substring with longest repeating character

Question

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 return 6 and "a".
One of the best concatenations is words[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"]))

Answer 1

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:

• Original(?) problem on Codility (specifies that the length of the input can be <= 100000, which would reject the brute force approach here)
• Concatenate the words to obtain a single word with the longest possible substring composed of a single letter on Stack Overflow which has some O(n) suggestions that seem promising, but I haven't gotten around to verifying.
• Concatenate words in such a way as to obtain the longest possible sub-string of the same letter on Code Review SE from the same author of the SO post, with some additional insights in the comments and answers.

Answer 2

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"]))