Home

Reduction

Answer

O(n^2) time:

function StringReduction(str) { flag = true; while (flag) { flag = false; for (let i = 1; i < str.length; i++) { if (/ab|ba/i.test(`${str[i - 1]}${str[i]}`)) { str = str.replace(/ab|ba/i, 'c'); flag = true; } else if (/bc|cb/i.test(`${str[i - 1]}${str[i]}`)) { str = str.replace(/bc|cb/i, 'a'); flag = true; } else if (/ac|ca/i.test(`${str[i - 1]}${str[i]}`)) { str = str.replace(/ac|ca/i, 'b'); flag = true; } } } return str.length; }

O(n) time:

function StringReduction(str) { flag = true; while (flag) { flag = false; if (/ab|ba|ab|ba|ac|ca/i.test(str)) { str = str.replace(/ab|ba/i, 'c'); str = str.replace(/bc|cb/i, 'a'); str = str.replace(/ac|ca/i, 'b'); flag = true; } } return str.length; }