Coding Challenge: Remove Characters from String

Coding challenges are not only a fact of life for technical interviews and assessments, they are also fun! Mastering the process of solving coding challenges will give you the confidence to go into any technical interview or assessment and succeed. And we all know confidence is half the battle when interviewing. In this series, I am tackling various coding challenges and explaining my process along the way. For this challenge, I am using Javascript since that is my primary focus these days.

The Challenge: Remove Characters from String

The Remove Characters from String challenge is pretty easy but what they are really testing is your optimization skills.

Given an array of characters and a string, write a function to return the string with all the characters in the array removed.

Time Management

Time management is an important aspect of interviews and assessments and should be taken into consideration right from the start. It is better to have completely coded correct answers to all the challenges than to have one perfect answer and the rest unfinished. For that reason, I usually start with the "brute force" method. Just get a solution down. Worry about efficiency and elegance later. And yes, Big $\mathcal{O}$ considerations come after we get through the brute force phase.

Brute force

Let's just brute force this puppy:

function removeChars(chars, B) {
  let output = '';
  for (const ltr of B) {
    if (!chars.includes(ltr)) {
      output += ltr;
    }
  }
  return output;
}

Looks good, but on closer inspection, we can see this is $\mathcal{O}(n*m)$. We have to do one iteration for the array of characters and one for the length of the string. As each one gets bigger, this gets out of control pretty fast. We better optimize that before submitting.

Refactor

Our brute force version has a Big $\mathcal{O}$ of $\mathcal{O}(n*m)$. Not good. Let's try again.

function removeChars(chars, B) {
  const charSet = new Set(chars);
  let output = '';
  for (const ltr of B) {
    if (!charSet.has(ltr)) {
      output += ltr;
    }
  }
  return output;
}

Time Complexity Analysis

Creating the Set: const charSet = new Set(chars);

• Creating a set from an array chars involves iterating through the array, which takes $\mathcal{O}(m)$ time, where m is the length of chars.

Iterating Through String B: for (const ltr of B) { ... }

• This loop runs n times, where n is the length of B.

Checking Set Membership and Concatenating String:

• charSet.has(ltr) is an $\mathcal{O}(1)$ operation.
• output += ltr takes $\mathcal{O}(k)$ time where k is the current length of output (though JavaScript engines optimize string concatenation to amortize the cost).

Combining these steps:

• Creating the set: $\mathcal{O}(m)$
• Iterating through B and performing $\mathcal{O}(1)$ checks and string concatenations: $\mathcal{O}(n * k)$ (amortized cost is O(n))

Therefore, the overall time complexity is $\mathcal{O}(n+m)$.

Space Complexity Analysis

• Set Storage: charSet requires $\mathcal{O}(m)$ space to store the unique characters from chars.
• Output String: output will store up to n characters, so it requires $\mathcal{O}(n)$ space.

Therefore, the space complexity is $\mathcal{O}(n+m)$.

Optimizations

The function is already optimized for time and space complexity. However, there are a few minor improvements that can be made for clarity and performance:

String Builder: Using an array to accumulate characters and joining them at the end can be more efficient than concatenating strings repeatedly.

Here is the function with this improvement:

function removeChars(chars, B) {
  const charSet = new Set(chars);
  const output = [];
  for (const ltr of B) {
    if (!charSet.has(ltr)) {
      output.push(ltr);
    }
  }
  return output.join('');
}

This offers a slight optimization over the string concatenation method. Worth the effort for a coding challenge as long as time allows.

Conclusion

This coding challenge introduced us to the idea of complexity and optimization. We'll need those as we tackle tougher challenges.

See Also

• Github Repo: Remove Characters from String
• Github Repo: Coding Challenges