Understanding time complexity to replace string characters-CodePudding

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)
}

CodePudding user response：

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).

CodePudding user response：

The indexOf() method returns the first index at which a given element can be found in the array, or -1 if it is not present, so the worst case will be O(N), and you replaceAll inside the loop so the Big-O is O(N), the total Will O(N^2)

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf