algorithm - Implement a function in JavaScript to determine if a word can be formed from another word by removing repeated letters

Question

I am trying to implement a function in JavaScript called canBeFormed that does this:

const string1 = 'hellooooolooo'
const string2 = 'hellolo'
canBeFormed(string1, string2) // true since by deleting the repeated chars 'o' and 'l' we can form the word 'hellolo'

So if string2 can be formed by string1 if string1 remove some duplicate chars then we return true

I cannot seem to come up with a workable solution to this problem. Can someone give this a shot?

Btw, someone mentioned that this could be solved by dfs + backtracking. Can someone give that approach a try?

To clarify, this function return true if it can form a word from the second string provided by removing one or more repeated letters.

So canBeFormed("heellolo", "hellooooolooo") will return false. canBeFormed("abc", "ac") will return false

Answer 1

My understanding is that the function should return true if, and only when, the first string can be formed from the second by repeating (consecutively) some characters already present in the first.

The algorithm can be greedy and no backtracking is needed.

function canBeFormed(a, b) {
    let i = 0;
    for (let ch of b) {
        if (ch !== a[i]) {
            // Skip duplicate letters in a
            while (a[i] === a[i-1]) {
                if (++i >= a.length) return false;
            }
            if (ch !== a[i]) return false;
        }
        ++i;
    }
    // Remaining characters should be duplicates
    while (a[i] === a[i-1]) {
        if (++i >= a.length) return true;
    }
    return false;
}

console.log(canBeFormed("hellooooollooo","hellolo")); // true
console.log(canBeFormed("abbcc", "abc")); // true
console.log(canBeFormed("aaabbb", "aaabb")); // true
console.log(canBeFormed("helloooolloo","heellolo")); // false
console.log(canBeFormed("abc", "ac")); // false
console.log(canBeFormed("abbc", "ac")); // false
console.log(canBeFormed("ababc", "abc")); // false
console.log(canBeFormed("abbcca", "abc")); // false
console.log(canBeFormed("aab", "aaab")); // false