El truco de la pila para maximizar un número

Tenés una secuencia de dígitos y querés quedarte con exactamente k, respetando el orden original, de forma que el número resultante sea el más grande posible. La intuición de “agarrá los k dígitos más grandes” falla: en 291 con k = 2, los más grandes son 9 y 2, pero el máximo real es 91.

La clave es que un dígito grande vale más cuanto más a la izquierda esté. Entonces recorrés de izquierda a derecha con una pila, y cada vez que el dígito actual es mayor que el tope, sacás el tope — siempre que te queden descartes disponibles.

function maxKeeping(s, k) {
  let removals = s.length - k;
  const stack = [];
  for (const ch of s) {
    while (removals > 0 && stack.length && stack.at(-1) < ch) {
      stack.pop();
      removals--;
    }
    stack.push(ch);
  }
  return stack.slice(0, k).join('');
}

Corre en O(n) y es exacto, no una heurística.