Aká je zložitosť navrhnutého riešenia s odstraňovaním znakov a reverzom? Môžeme zlepšiť algoritmus?

Ak riešenie zahŕňa odstránenie znakov zo reťazca a následné jeho obrátenie, potom bude zvyčajne zložitosť závisieť od dĺžky reťazca n. Odstránenie znakov môže byť realizované v jednom prechode — O(n), obrátenie reťazca tiež O(n), takže celková časová zložitosť — O(n).

Je možné to zlepšiť? Ak to úloha umožňuje, operácie odstránenia a obrátenia je možné spojiť do jedného prechodu, napríklad prechádzaním reťazca od konca, súčasne filtrovaním znakov, čo umožní urobiť všetko v jednom prechode — stále O(n), ale s menším konštantným násobiteľom a menším využitím pamäti.

Príklad v Pythone:

s = "example"
# Odstránime znaky 'a' a 'e', potom obrátime
result = ''.join(c for c in reversed(s) if c not in {'a', 'e'})
print(result)  # Výstup: lpmx

Týmto spôsobom je algoritmus optimalizovaný spojením operácií, ale asymptotická zložitosť zostáva lineárna.