Optimális megoldás erre a feladatra?

Szerintem ennek semmi esetre sem lehet O(n) megoldása.

1) Nem tudod előre milyen prefixekket kell nézni és milyen mélységben (hány karakter hosszan)

2) Nem tudod, hogy hány azonos kategória lehet, ahogy "asd" vagy "xy" esetén. Csak utólag tudod meg mondani => Tehát keresni kell.

Mivel struktrúráról beszélünk, így fa építhető ki (akár több, más kezdő karakterrel) és meg kell nézni, hogy milyen mélyűek.

Tömören, témába nem mélyen belemenve ezt gondolom. Persze tévedhetek is és van O(n). De majd a tőlem okosabbak megcáfolnak vagy megerősítenek. :)