Understanding time complexity to replace string characters

Viewed 65

This is my solution in javascript to remove all occurrences of 'b' and 'ac' in a string but I am able to come up with time complexity esp. when removing all occurences for 'ac'. Could someone explain ?

function removeChars(input) {
  let result = input;

  
  result = result.replaceAll('b', '');   // tc = O(n) where n is length of string. string of all b's
  

  while(result.indexOf('ac') !== -1) {  // number of ac ? what if aacacacc
    result = result.replaceAll('ac', '');    // replaceAll has time complexity of O(n)
  }
  return result;  // space ~ O(n)
}

2 Answers

We can consider one of the most special cases: input = aaa...aaaccc...ccc.

Assume the input string has length n, there will be n / 2 occurences for 'ac'. The statement of result = result.replaceAll('ac', ''); will be executed n / 2 times. The time complexity of replaceAll() is O(n), thus the overall time complexity is O(n^2).

Related