Как повысить производительность этого алгоритма Javascript / взлома кода?

Коды символов ASCII / Unicode всех букв одного и того же регистра являются последовательными. Это позволяет провести важную оптимизацию: вы можете найти индекс символа в массиве подсчета символов по его символьному коду ASCII / Unicode. В частности, индекс символа c в массиве счетчика символов будет c.charCodeAt(0) - 'a'.charCodeAt(0). Это позволяет вам искать и изменять количество символов в массиве во времени O(1), что сокращает время выполнения алгоритма до O(n).

Основываясь на вашем описании, я предполагаю, что ввод - это строка (которая неизменна в javascript), и я не уверен, что именно означает «одна или две дополнительные переменные», поэтому, исходя из вашей реализации, я собираюсь предположить, что можно использовать O ( N) пробел. Чтобы улучшить временную сложность, я думаю, что реализации различаются в зависимости от различных требований к выводимой строке.

Предположение1: выводимая строка находится в том порядке, в котором она появляется в первый раз. например. «bcabcc» -> «bca»

Предположим, что длина s равна N, в следующей реализации используется пространство O (N) и время O (N).

 function removeDuplicates(s) {
    const set = new Set(); // use set so that insertion and lookup time is o(1)
    let res = "";
    for (let i = 0; i < s.length; i++) {
        if (!set.has(s[i])) {
            set.add(s[i]);
            res += s[i];
        }
    }
    return res;
  }

Предположение2: выводимая строка должна иметь возрастающий порядок.

Вы можете использовать быстрая сортировка для сортировки на месте, а затем перебрать отсортированный массив, чтобы добавить в результат последний элемент. Обратите внимание, что вам может потребоваться сначала разбить строку на массив. Таким образом, реализация будет использовать пространство O (N), а средняя временная сложность будет O (NlogN)

Предположение 3: результат является наименьшим в лексикографическом порядке среди всех возможных результатов. например. «bcabcc» -> «abc»

Следующая реализация использует пространство O (N) и время O (N).

const removeDuplicates = function(s) {
    const stack = []; // stack and set are in sync
    const set = new Set(); // use set to make lookup faster
    const lastPos = getLastPos(s);
    let curVal;
    let lastOnStack;

    for (let i = 0; i < s.length; i++) {
        curVal = s[i];
        if (!set.has(curVal)) {
            while(stack.length > 0 && stack[stack.length - 1] > curVal && lastPos[stack[stack.length - 1]] > i) {
                set.delete(stack[stack.length - 1]);
                stack.pop();
            }
            set.add(curVal);
            stack.push(curVal);
        }
    }
    return stack.join('');
};

const getLastPos = (s) => {
    // get the last index of each unique character
    const lastPosMap = {};
    for (let i = 0; i < s.length; i++) {
        lastPosMap[s[i]] = i;
    }
    return lastPosMap;
}

Есть небольшой трюк «без использования какого-либо дополнительного буфера», хотя я не вижу способа улучшить сложность O(n^2) без использования хэш-карты, чтобы определить, был ли замечен конкретный символ. Уловка состоит в том, чтобы пройти по буферу входной строки (предположим, что это массив JavaScript, поскольку строки в JavaScript неизменяемы) и перезаписать текущий символ следующим уникальным символом, если текущий символ является дубликатом. Наконец, отметьте конец результирующей строки нулевым символом.

Псевдокод:

i = 1
pointer = 1

while string[i]:
  if not seen(string[i]):
    string[pointer] = string[i]
    pointer = pointer + 1
  i = i + 1

mark string end at pointer

Функция seen может либо взять время O(n) и пространство O(1), либо время O(1) и пространство O(|alphabet|), если мы используем хэш-карту.

Я не понимал, что имел в виду:

...without using any additional buffer.

Поэтому я подумал, что попробую сделать это за один цикл, и позволю вам сказать мне, если это неправильно.

Я работал на основе того, что предоставленная вами функция дает правильный результат, вы просто искали, чтобы она работала быстрее. Приведенная ниже функция дает правильный результат и работает намного быстрее с любой большой строкой с большим количеством дубликатов, которые я ей добавляю.

function removeDuplicates(originalString) {
    let outputString = '';
    let lastChar = '';
    let lastCharOccurences = 1;

    for (let char = 0; char < originalString.length; char++) {
        outputString += originalString[char];

        if (lastChar === originalString[char]) {
            lastCharOccurences++;
            continue;
        }
        
        if (lastCharOccurences > 1) {
            outputString = outputString.slice(0, outputString.length - (lastCharOccurences + 1)) + originalString[char];
            lastCharOccurences = 1;
        }

        lastChar = originalString[char];
    }

    console.info("The string with removed duplicates is:", outputString)
}

removeDuplicates("Hippotamuus")

Опять же, извините, если я неправильно понял сообщение ...