A function to remove characters from a string

Posted on

Problem

I wanted to write a function to remove a set of characters from a string in JavaScript.

I came up with this.

How can it be improved in terms of time/space complexity?

function remove(str, chars) {
    var set = new Set(chars); // looking up presence of char is O(1)
    var arr = [...str]; // operate on an arrray rather than a string to avoid unneccessary string copying
    // What follows is O(N) I think...
    return arr.reduce((p,c) => {
        if(set.has(c)) {
            return p;
        }
        p.push(c);
        return p;
    }, []).join('');
}

remove('hello world', 'el') === 'ho word';

Solution

  • Don’t abuse reduce. Reduce should be used when you want to reduce the list. Take using reduce to find the sum of a list: [1, 2, 3].reduce((a, b) => a + b, 0).
  • Use filter if you want to filter a list. arr.filter(i => !set.has(i)).
  • You may want to instead use regex.replace. However, it’d require checking your chars for any regex escape stuff.

    However if you ignore that, it could be as easy as:

    function remove(str, chars) {
      return str.replace(new RegExp(`[${chars}]`, 'g'), '');
    }
    

Otherwise using the above, for O(n)

O(n)

time and space complexity, could get you:

function remove(str, chars) {
    var set = new Set(chars);
    return [...str].filter(i => !set.has(i)).join('');
}

Leave a Reply

Your email address will not be published. Required fields are marked *