I hope all is well on your end!

I encountered an interesting sequence problem and I've been struggling to solve it: "Find the most common sequence across the array of strings with a specific number of characters."

Input: (["abc", "usbc", "bcde"], 2) Output: "bc"

Input: (["terrific, specific"], 4) Output: "ific"

Here's what I have so far:

function commonSubstring(array, length) {
  let popular = '';
  let seq = []
  let map = {}

  for (let i = 0; i < array.length; i  ) {
    for (let j = 0; j < array[i].length; j  ) {
      const str = array[i].slice(j, j length)
      if (str.length === length && array[i].includes(str)) {
        seq.push(str)
      }
      if (array[i].includes(seq[j]) && !map[seq[j]]) {
        map[seq[j]] = 1
        // console.log(seq[j])
      } else {
        map[seq[j]]  
        j  
      }
    }
  }
  console.log(map)
  return popular
}

What I was trying to do is go through each string element and find common sequences and I added a map to have a point system, then ultimately find the key that has the most points and return that key.

Honestly, I'm a bit lost. How do I efficiently solve this problem?

Thank you!

CodePudding user response：

here is a solution using a for loop and recursive call

const getSequence = (list, length, check) => {
  if(!list.length || (check && check.length < length)) {
   return false;
  }
  let result = check || list[0];  //setting first item as a result
  let found = true;

  let i;
  for(i = 1; i<list.length; i  ) {
    if(list[i].indexOf(result.substring(0, length)) == -1) {
      found = false;
      break;
    }
  }
  if(!found) {
     let val = getSequence(list, length, result.substring(1, result.length)) //calling same function by removing first char 
     if(val) {
      return val;
     }
  }
  else {
    return result.substring(0, length);
  }
}


console.log(getSequence(["abc", "usbcj", "bcdeh"], 2))
console.log(getSequence(["terrific", "specific"], 4))
console.log(getSequence(["test", "text"], 2))

<iframe name="sif1" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

CodePudding user response：

This is a modification of your code that implements the suggestions in my comment above:

• Shorten the inner (j) loop to only loop through offsets that can hold the length in the current string,
• Remove the length checks, as they are no longer needed,
• Remove the checks for the substring in the array as they are unneeded.

I also added the max-search so that it would return the answer:

function commonSubstring(array, length) {
  let popular = '';
  let seq = []
  let map = {}

  for (let i = 0; i < array.length; i  ) {
    for (let j = 0; j < array[i].length - length   1; j  ) {
      const str = array[i].slice(j, j length)
      if (!map[str]) {
        map[str] = 1
      } else {
        map[str]  
      }
    }
  }
  // console.log(map)
  
  let maxv = 0;
  for(let prop in map) {
    if(map[prop] > maxv) {
      popular = prop;
      maxv = map[prop];
    }   
  }
  return popular
}

console.log(commonSubstring(["abc", "usbcj", "bcdeh"], 2))
console.log(commonSubstring(["terrific", "specific"], 4))
console.log(commonSubstring(["test", "text"], 2))

<iframe name="sif2" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

This runs in O(n*m) where n is the total number of input characters and m is the length parameter. As far as I know this is the best CPU complexity you can get for this problem. As for implementation efficiency, this should be pretty close to the best possible.