Getting time and space complexity of a JS function

user_16400843 0
Viewed 82

Here' i have a solution of a problem of removing consecutive duplicate characters. But i need to know the time and space complexity of this solution.

Here's the function:

function removeAdjacentDuplicates(str){
    for (let i = 0; i< str.length -1; i++){
        if(str[i] === str[i+1] && i+2==str.length){
            return str.substr(0,i);
        } else if(i+2==str.length ||str=="" || str.length==0){
            return str;
        } else if (str[i] === str[i+1]){
            return removeAdjacentDuplicates(str.substr(0,i)+str.substr(i+2,(str.length)-(i+2))); 
        }
    }
};

//removeAdjacentDuplicates('abbc') returns 'ac'

I'm guessing it should be O(n) for both because for each input the function needs to loop over the whole. Also suggestion for making the function better would be appreciated too.

space-complexity time-complexity javascript
1 Answers

I suppose a simple reduce will be sufficient and not too complex here.

How to determine complexity is explained nicely here. Furthermore, there are plenty of articles to be found on the subject (e.g. here or here).

See also

console.log(`original: abba and,, sommmme of thaat ook??`, ` `);
console.log(`removeAdjacentDuplicates: ${
  removeAdjacentDuplicates('abba and,, sommmme of thaat ook??')}`);
console.log(`removeDuplicateCharacterPairs: ${
  removeDuplicateCharacterPairs('abba and,, sommmme of thaat ook??')}`);
console.log(`RemoveConcurrentCharacters: ${
    RemoveConcurrentCharacters([...'abba and,, sommmme of thaat ook??'])}`);
console.log(`RemoveConcurrentCharactersReducer: ${
  RemoveConcurrentCharactersReducer([...'abba and,, sommmme of thaat ook??'])}`);

// this removes one of duplicate character pairs
function removeAdjacentDuplicates(str) {
  return str.split('')
    .reduce((acc, val) =>
      val === acc.slice(-1) ? acc : acc + val, '');
}

// this removes actual duplicate pairs, 
// but the result may contain new duplicates
function removeDuplicateCharacterPairs(str, result = []) {
  str = str.split("");
  const first = str.shift();
  str.length && first !== str[0] && result.push(first) || str.shift();
  return str.length ?
    removeDuplicateCharacterPairs(str.join(""), result) :
    result.join("");
}

// this removes duplicate pairs. When the result
// contains new duplicate pairs removes them too
// so the result will not contain any duplicate
// character pair
function RemoveConcurrentCharacters(arr) {
  let result = [];
  for (let i = 0; i < arr.length; i += 1) {
    const len = result.length - 1;

    i < 1 && result.push(arr[i]);

    if (i > 0) {
      arr[i] !== result[len] &&
        result.push(arr[i]) ||
        result.splice(len, 1);
    }
  }
  return result.join("");
};

// making a round trip: RemoveConcurrentCharacters can be
// condensed using a reducer method.
function RemoveConcurrentCharactersReducer(arr) {
  return arr.reduce((acc, val) =>
      !acc.length ? [val] : val === acc[acc.length-1] ? 
        acc.slice(0, -1) : [...acc, val], [])
    .join("");
};

NICon_581860
Related