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!
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))This is a modification of your code that implements the suggestions in my comment above:
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))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.