Cómo evitar los caracteres repetitivos de una cadena

Por O (1) complejidad espacial, supongo que te refieres a O (1) espacio adicional.

Esta solución parece un poco extraña, pero debería funcionar de todos modos.

Por simplicidad, voy a suponer que todos los caracteres están en minúsculas
Asigna cada uno de los 26 caracteres a un booleano. Inicialmente, todos están configurados en falso. (Use una matriz 2D o una tabla hash.
Iterar a través de cada personaje en la cadena

Busca el personaje. Si el valor correspondiente es falso , establezca el valor en verdadero . Luego, imprima el carácter sin espacio o carácter de nueva línea
Si el valor correspondiente es verdadero, bueno, hemos visto el personaje, así que no hacemos nada.

En pseudocódigo:

map = {‘a’: falso, ‘b’: falso, ‘c’: falso …}
str = “mississippi”

para personaje en str:
if map [character] == false:
printf (“% c”, caracter) // Sin nueva línea o espacio
mapa [caracter] = verdadero

Un pseudoanálisis le indicaría que estamos iterando sobre elementos de longitud (str) . Llamemos length (str), N por simplicidad. En otras palabras, tenemos iteraciones Ө (N) .

En cada iteración, estamos haciendo una búsqueda de tabla hash o matriz, lo que debería llevar tiempo Ө (1) . Por lo tanto, es justo decir que el tiempo total de ejecución es Ө (N) • Ө (1). Que es igual a Ө (N) .

En lo que respecta a la complejidad espacial, el mapa o la matriz 2D ocupará dos unidades de espacio para cada uno de los 26 caracteres (52 si está haciendo mayúsculas por separado o lo que sea del tamaño de su conjunto de caracteres). Como el tamaño del juego de caracteres es constante y el número de unidades de espacio es constante, la memoria que consumen estos es Ө (1)

Por lo tanto, nuestra complejidad espacial es Ө (1).

En Python puro,

inicio = 65 # El carácter inicial es ‘A’
end = 122 # El carácter final es ‘z’

map = {char (i): falso para i en rango (inicio, (final + 1))}
str = ‘mississipi’

para personaje en str:
if map [character] == False:
print (caracter, final = ”)
mapa [personaje] = Verdadero

EDITAR 1:

Aquí hay un código C ++ para lo mismo:

#include
#include
#include

usando el espacio de nombres estándar;

int main () {

int inicio = 65;
int end = 122;

char str [11] = “mississippi”;
unordered_map map;

for (int i = start; i <= end; i ++) {

mapa [i] = falso;

}

para (int i = 0; i <11; i ++) {

if (mapa [str [i]] == falso) {
printf (“% c”, str [i]);
mapa [str [i]] = verdadero;
}

}

devuelve 0;

}