En este artículo, se exploran soluciones a varios problemas de LeetCode relacionados con la estadística de caracteres en cadenas, utilizando estructuras de datos como mapas hash, colas, ordenamiento y operaciones a nivel de bit.
387. Primer carácter único en una cadena
Solución mediante array de conteo: Se crea un array para registrar la frecuencia de cada carácter, luego se recorre la cadena para encontrar el primer carácter con frecuencia uno.
class Solucion {
public static int primerCaracterUnico(String cadena) {
int n = cadena.length();
int[] contador = new int[26];
for (int idx = 0; idx < n; idx++) {
contador[cadena.charAt(idx) - 'a']++;
}
for (int idx = 0; idx < n; idx++) {
if (contador[cadena.charAt(idx) - 'a'] == 1) {
return idx;
}
}
return -1;
}
}
Solución con cola: Se utiliza un mapa hash para rastrear posiciones y una cola para mantener el orden de los caracteres únicos, eliminando los repetidos a medida que se avanza.
class Solucion {
public int primerCaracterUnico(String cadena) {
Map<character integer=""> mapa = new HashMap<>();
Queue<par> cola = new LinkedList<>();
int longitud = cadena.length();
for (int i = 0; i < longitud; i++) {
char ch = cadena.charAt(i);
if (!mapa.containsKey(ch)) {
mapa.put(ch, i);
cola.offer(new Par(ch, i));
} else {
mapa.put(ch, -1);
while (!cola.isEmpty() && mapa.get(cola.peek().caracter) == -1) {
cola.poll();
}
}
}
return cola.isEmpty() ? -1 : cola.poll().posicion;
}
class Par {
char caracter;
int posicion;
Par(char caracter, int posicion) {
this.caracter = caracter;
this.posicion = posicion;
}
}
}</par></character>
389. Encontrar la diferencia
Solución con array de frecuencia: Se compara la frecuencia de caracteres entre las cadenas s y t; la diferencia indica el carácter adicional en t.
class Solucion {
public static char encontrarDiferencia(String s, String t) {
int[] frecuencia = new int[26];
int lenS = s.length();
int lenT = t.length();
for (int i = 0; i < lenT; i++) {
if (i < lenS) {
frecuencia[s.charAt(i) - 'a']++;
}
frecuencia[t.charAt(i) - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (frecuencia[i] != 0) {
return (char) ('a' + i);
}
}
return ' ';
}
}
Solución por suma de códigos ASCII: Se calcula la suma de los valores ASCII de ambas cadenas; la diferencia revela el carácter extra.
public char encontrarDiferencia(String s, String t) {
return (char) (t.codePoints().sum() - s.codePoints().sum());
}
Solución con operación XOR a nivel de bit: Al concatenar las cadenas, el carácter que aparece un número impar de veces se identifica mediante XOR, ya que los pares se anulan.
class Solucion {
public char encontrarDiferencia(String s, String t) {
int resultado = 0;
for (int i = 0; i < s.length(); i++) {
resultado ^= s.charAt(i);
}
for (int i = 0; i < t.length(); i++) {
resultado ^= t.charAt(i);
}
return (char) resultado;
}
}
383. Nota de rescate
Solución con array de conteo: Se verifica si la revista contiene suficientes caracteres para formar la nota, contando frecuencias y comparando.
class Solucion {
public boolean puedeConstruir(String nota, String revista) {
int[] contador = new int[26];
int lenNota = nota.length();
int lenRevista = revista.length();
if (lenNota > lenRevista) {
return false;
}
for (int i = 0; i < lenRevista; i++) {
contador[revista.charAt(i) - 'a']++;
if (i < lenNota) {
contador[nota.charAt(i) - 'a']--;
}
}
for (int i = 0; i < 26; i++) {
if (contador[i] < 0) {
return false;
}
}
return true;
}
}
242. Anagrama válido
Solución mediante array de frecuencia: Se asegura que ambas cadenas tengan la misma longitud y que la diferencia de frecuencias sea cero para todos los caracteres.
class Solucion {
public boolean esAnagrama(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] cuenta = new int[26];
for (int i = 0; i < s.length(); i++) {
cuenta[s.charAt(i) - 'a']++;
cuenta[t.charAt(i) - 'a']--;
}
for (int val : cuenta) {
if (val != 0) {
return false;
}
}
return true;
}
}
Solución por ordenamiento: Convierte las cadenas en arrays de caracteres, los ordena y compara directamente.
class Solucion {
public boolean esAnagrama(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] arrS = s.toCharArray();
char[] arrT = t.toCharArray();
Arrays.sort(arrS);
Arrays.sort(arrT);
return Arrays.equals(arrS, arrT);
}
}
49. Agrupar anagramas
Solución con clave ordenada: Se ordenan los caracteres de cada cadena para crear una clave única, que se usa en un mapa hash para agrupar anagramas.
class Solucion {
public List<list>> agruparAnagramas(String[] cadenas) {
Map<string list="">> mapa = new HashMap<>();
for (String str : cadenas) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String clave = new String(chars);
List<string> lista = mapa.getOrDefault(clave, new ArrayList<>());
lista.add(str);
mapa.put(clave, lista);
}
return new ArrayList<>(mapa.values());
}
}</string></string></list>
Solución con clave de conteo: En lugar de ordenar, se genera una clave basada en la frecuencia de caracteres, concatenando conteos positivos.
class Solucion {
public List<list>> agruparAnagramas(String[] cadenas) {
Map<string list="">> mapa = new HashMap<>();
for (String str : cadenas) {
int[] frecuencias = new int[26];
for (int i = 0; i < str.length(); i++) {
frecuencias[str.charAt(i) - 'a']++;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
if (frecuencias[i] > 0) {
sb.append((char) ('a' + i));
sb.append(frecuencias[i]);
}
}
String clave = sb.toString();
List<string> lista = mapa.getOrDefault(clave, new ArrayList<>());
lista.add(str);
mapa.put(clave, lista);
}
return new ArrayList<>(mapa.values());
}
}</string></string></list>
451. Ordenar caracteres por frecuencia
Solución con conteo y ordenamiento: Se cuentan las frecuencias, se ordenan los caracteres por frecuencia descendente y se construye la cadena resultante.
class Solucion {
public String ordenarPorFrecuencia(String cadena) {
Map<character integer=""> mapa = new HashMap<>();
for (char c : cadena.toCharArray()) {
mapa.put(c, mapa.getOrDefault(c, 0) + 1);
}
List<character> lista = new ArrayList<>(mapa.keySet());
Collections.sort(lista, (a, b) -> mapa.get(b) - mapa.get(a));
StringBuilder resultado = new StringBuilder();
for (char c : lista) {
int freq = mapa.get(c);
for (int i = 0; i < freq; i++) {
resultado.append(c);
}
}
return resultado.toString();
}
}</character></character>
Solución con buckets de frecuencia: Se crean cubetas para cada frecuencia posible, se llenan con caracteres y se construye la cadena desde la cubeta más frecuente.
class Solucion {
public String ordenarPorFrecuencia(String cadena) {
Map<character integer=""> mapa = new HashMap<>();
int maxFreq = 0;
for (char c : cadena.toCharArray()) {
int freq = mapa.getOrDefault(c, 0) + 1;
mapa.put(c, freq);
maxFreq = Math.max(maxFreq, freq);
}
StringBuilder[] cubetas = new StringBuilder[maxFreq + 1];
for (int i = 0; i <= maxFreq; i++) {
cubetas[i] = new StringBuilder();
}
for (Map.Entry<character integer=""> entrada : mapa.entrySet()) {
cubetas[entrada.getValue()].append(entrada.getKey());
}
StringBuilder resultado = new StringBuilder();
for (int i = maxFreq; i > 0; i--) {
StringBuilder cubeta = cubetas[i];
for (int j = 0; j < cubeta.length(); j++) {
char c = cubeta.charAt(j);
for (int k = 0; k < i; k++) {
resultado.append(c);
}
}
}
return resultado.toString();
}
}</character></character>