Este ejercicio suele aparecer en entrevistas laborales de Amazon y de algunas otras empresas. Acá vemos algunas opciones de resolución, con Java. ¿Se te ocurre alguna otra?
Click aquí para una versión accesible de la infografía (apta para lectores electrónicos)
Dado un string compuesto solo por letras minúsculas, hallar el primer carácter que no se repite. Si no existe, retornar “_”.
Cuatro posibles soluciones en Java.
Opción 1: por “fuerza bruta”. Complejidad algorítmica: O(N2)
static char primerCaracterNoRepetido_fuerzaBruta(String cadena) {
for (int i = 0; i < cadena.length(); i++) {
boolean repetido = false;
for (int j = 0; j < cadena.length(); j++) {
if (cadena.charAt(i) == cadena.charAt(j) && (i != j)) {
repetido = true;
}
}
if (!repetido)
return cadena.charAt(i);
}
return '_';
}
Click aquí para una versión accesible de la infografía (apta para lectores electrónicos)
Opción 2: con métodos predefinidos. Complejidad algorítmica: O(N2)
static char primerCaracterNoRepetido_metodosPredefinidos(String cadena) {
for (int i = 0; i < cadena.length(); i++) {
if (cadena.indexOf(cadena.charAt(i)) == cadena.lastIndexOf(cadena.charAt(i))) {
return cadena.charAt(i);
}
}
return '_';
}
Click aquí para una versión accesible de la infografía (apta para lectores electrónicos)
Opción 3: con hashmap. Complejidad algorítmica: O(N)
static char primerCaracterNoRepetido_hashMap(String cadena) {
HashMap<Character, Integer> ocurrencias = new HashMap();
for (int i = 0; i < cadena.length(); i++) {
char c = cadena.charAt(i);
if (ocurrencias.containsKey(c)) {
ocurrencias.put(c, ocurrencias.get(c) + 1);
} else {
ocurrencias.put(c, 1);
}
}
for (int i = 0; i < cadena.length(); i++) {
char c = cadena.charAt(i);
if (ocurrencias.get(c) == 1)
return c;
}
return '_';
}
Click aquí para una versión accesible de la infografía (apta para lectores electrónicos)
Opción 4: con un arreglo asociado. Complejidad algorítmica: O(N)
static char primerCaracterNoRepetido_arregloAsociado(String cadena) {
int[] ocurrencias = new int[26];
for (char c : cadena.toCharArray()) {
ocurrencias[c - 'a']++;
}
for (char c : cadena.toCharArray()) {
if (ocurrencias[c - 'a'] == 1)
return c;
}
return '_';
}