Este problema consiste en encontrar la contraseña más larga en un conjunto de cadenas donde todas sus versiones truncadas por el final también existen en el conjunto. Se requiere manejar grandes volúmenes de datos de manera eficiente.

Análisis del problema

Dado un conjunto de cadenas de letras minúsculas, debemos identificar la cadena más larga que cumpla con la condición de que al ir eliminando caracteres desde el final uno a uno, cada subcadena resultante también se encuentre en el conjunto original. En caso de haber múltiples caddenas de la misma longitud máxima, se debe devolver la que sea lexicográficamente mayor. Si ninguna cadena cumple la condición, se devuelve una cadena vacía.

Enfoque de solución

La solución óptima combina preprocesamiento y ordenamiento:

• Almacenar todas las cadenas en un conjunto hash para verificación rápida.
• Filtrar candidatos válidos de manera incremental: una cadena es válida si su prefijo (sin el último carácter) ya es válido.
• Ordenar las cadenas por longitud ascendente permite procesarlas en el orden correcto.
• Entre las cadenas válidas más largas, selecionar la lexicográficamente mayor.

Implementación en Java

import java.util.*;
import java.util.stream.*;

public class BuscadorContraseña {
    public static String encontrarContraseña(List<String> contraseñas) {
        Set<String> conjunto = new HashSet<>(contraseñas);
        List<String> ordenadas = contraseñas.stream()
            .distinct()
            .sorted(Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()))
            .collect(Collectors.toList());
        
        Set<String> válidas = new HashSet<>();
        
        for (String pwd : ordenadas) {
            if (pwd.length() == 1) {
                válidas.add(pwd);
            } else {
                String prefijo = pwd.substring(0, pwd.length() - 1);
                if (válidas.contains(prefijo)) {
                    válidas.add(pwd);
                }
            }
        }
        
        return válidas.stream()
            .max(Comparator.comparingInt(String::length).thenComparing(Comparator.reverseOrder()))
            .orElse("");
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] entradas = scanner.nextLine().split(" ");
        System.out.println(encontrarContraseña(Arrays.asList(entradas)));
    }
}

Implementación en Python

def buscar_contraseña(contraseñas):
    únicas = sorted(set(contraseñas), key=lambda x: (len(x), x))
    válidas = set()
    
    for pwd in únicas:
        if len(pwd) == 1:
            válidas.add(pwd)
        elif pwd[:-1] in válidas:
            válidas.add(pwd)
    
    if not válidas:
        return ""
    
    return max(válidas, key=lambda x: (len(x), x))

if __name__ == "__main__":
    datos = input().split()
    print(buscar_contraseña(datos))

Implementación en JavaScript

function hallarContraseña(contraseñas) {
    const únicas = [...new Set(contraseñas)].sort((a, b) => 
        a.length - b.length || a.localeCompare(b));
    const válidas = new Set();
    
    únicas.forEach(pwd => {
        if (pwd.length === 1) {
            válidas.add(pwd);
        } else {
            const prefijo = pwd.slice(0, -1);
            if (válidas.has(prefijo)) {
                válidas.add(pwd);
            }
        }
    });
    
    if (válidas.size === 0) return "";
    
    return Array.from(válidas)
        .sort((a, b) => b.length - a.length || b.localeCompare(a))[0];
}

const entrada = readline().split(' ');
console.log(hallarContraseña(entrada));

Implementación en C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_set>
using namespace std;

string buscarContraseña(vector<string>& contraseñas) {
    unordered_set<string> conjunto(contraseñas.begin(), contraseñas.end());
    vector<string> ordenadas(conjunto.begin(), conjunto.end());
    
    sort(ordenadas.begin(), ordenadas.end(), [](const string& a, const string& b) {
        return a.length() < b.length() || (a.length() == b.length() && a < b);
    });
    
    unordered_set<string> válidas;
    
    for (const auto& pwd : ordenadas) {
        if (pwd.length() == 1) {
            válidas.insert(pwd);
        } else {
            string prefijo = pwd.substr(0, pwd.size() - 1);
            if (válidas.count(prefijo)) {
                válidas.insert(pwd);
            }
        }
    }
    
    if (válidas.empty()) return "";
    
    return *max_element(válidas.begin(), válidas.end(), [](const string& a, const string& b) {
        return a.length() < b.length() || (a.length() == b.length() && a < b);
    });
}

int main() {
    string línea;
    getline(cin, línea);
    stringstream ss(línea);
    vector<string> entradas;
    string token;
    while (ss >> token) entradas.push_back(token);
    
    cout << buscarContraseña(entradas) << endl;
    return 0;
}

Análisis de complejidad

Todas las implementaciones tienen complejidad temporal O(n log n) por el ordenamiento y espacial O(n) para el almacenamiento. El preprocesamiento garantiza verificaciones O(1) mediante conjuntos hash. El enfoque es escalable para entradas grandes dentro de los límites del problema (10^5 cadenas).

Casos de prueba

• Entrada: "a ab abc abcd" → Salida: "abcd"
• Entrada: "h he hel hell hello" → Salida: "hello"
• Entrada: "b bw bww bwwl bwwln bwwlm" → Salida: "bwwln"
• Entrada: "x xy xyz" → Salida: "xyz"
• Entrada: "a b c" → Salida: "c"