Is Unique

Implementa un algoritmo que determine si en un String todos sus caracteres son unicos.

Una vez lo resuelvas, como lo implementarias si no puedes usar otras estructuras de datos adicionales como Arrays, etc?

👉 Link aquí hacia el repo para solucionar el problema

👌 Tips

Intenta con un HashTable

Podrias intentarlo con un Bit Vector?

Podrias resolverlo en un tiempo 0(N log N )?

👊 Solución 1

Una solucion muy sencilla seria crear una array de booleans, en donde conseguiriamos la posicion del caracter en el alfabeto, y en esa posicion en el array de booleans lo convertiriamos a true. Si true ya existe en esa posicion del array, significa que hemos repetido de caracter.

boolean isUnique(String s) {
    if (s.length() > 128) return false;

    boolean[] set = new boolean[128];
    for (int i = 0; i < s.length(); i++) {
        int v = s.charAt(i);
        if (set[v]) {
            return false;
        }
        set[v] = true;
    }
    return true;
}

La complejidad en el tiempo de esta solucion es de 0 (N), en donde N es string.length().

👊 Solución 2

Podriamos reducir la utilizacion del espacio usando un BitVector en forma de Int.

Si asumimos que solamente utilizaremos las letras de la "a" a la "z" en minusculas, no necesitaremos mas de 28 banderas, que se encuentran en un Int.

Esta solucion es muy similar a la anterior, pero en vez de un Array con 128 espacios, usamos un BitWise Operator para encender las banderas de 0s a 1s.

boolean isUniqueBitVector(String s) {
    int checker = 0;
    for (int i = 0; i < s.length(); i++) {
        int v = s.charAt(i);
        if ((checker & (1 << v)) > 0) {
            return false;
        }
        checker |= (1 << v);
    }
    return true;
}

---

Pregunta prestada del libro "Cracking the coding interview”