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?

💻 Código ejecutable

▶️ Si te interesa ver más ejercicios de entrevistas laborales y su resolución paso a paso, visita este video

Opción 1: fuerza bruta

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 '_';
}


 

Opción 2: métodos predefinidos

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 '_';
}


 

Opción 3: hashmap

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 '_';
}


 

Opción 4: arreglo asociado

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 '_';
}