3. Íš zrozumiteľne? vzorové riešenie

abba

1

abcbaccf

3

abacaddc

2

Bruteforce

Na vyriešenie prvej sady postačovalo jednoduché prehľadávanie všetkých možných sekvencií prehľadávaní bruteforceom. To sa dá rekurzívne implementovať v časovej zložitosti \(O(n^4)\) (rozmyslite si prečo!).

Niečo lepšie

Stavy dynamiky

Namiesto ukladania všetkých podreťazcov si vytvoríme jeden zoznam \(dp[]\) veľkosti \(n+1\), kde:

• \(dp[i]\) = minimálny počet krokov na vymazanie podreťazca \(string[i:]\)
• \(dp[n] = 0\) (prázdny reťazec nepotrebuje žiadne kroky)

Smer výpočtu

Riešime problémy od najmenších k najväčším.
Ideme od konca reťazca k začiatku. Keď už máme pre nejaký suffix vypočítané hodnoty \(dp\), vieme túto hodnotu vypočítať pre pozíciu hneď pred ním – pozrieme si, aké je na tejto pozícií písmenko a nájdeme všetky zhodné písmenká v suffixe. Následne môžeme pre každú takúto zhodu úsek po ňu zmazať a potom zopakovať postup, ktorý sme našli pre \(dp\) nasledujúcej pozície.

Teda \(dp[i] = \min_{j \in \{i+1, ..., n\} \land s[j] = s[i]} (dp[j] + 1)\).

word = input().strip()
n = len(word)

dp = [float('inf')] * (n + 1)
dp[n] = 0 

for start in range(n - 1, -1, -1):
	first_char = word[start]
	for i in range(start, n):
		if word[i] == first_char:
			dp[start] = min(dp[start], 1 + dp[i + 1])

print(dp[0])

Zložitosť riešenia

• Časová zložitosť: \(O(n^2)\), kde \(n\) je dĺžka vstupného reťazca. To preto, lebo pre každý znak prechádzame všetky nasledujúce znaky a \(1 + 2 + ... + n = \frac{n(n+1)}{2} \in O(n^2)\).
• Pamäťová zložitosť: \(O(n)\).

Optimálne riešenie

Všimnime si, že bottleneck predošlého riešenia je to, že pre každý znak prehľadávame všetky znaky, s ktorými by sme ho mohli spojiť. Avšak, to ktorý z tých znakov si skutočne vyberieme je určené jedinou konštantnou hodnotou – minimálnou príslušnou hodnotou \(dp\). Avšak evidentne keď už si raz nevyberieme nejakú pozíciu, znamená to že sme našli lepšiu. Ale tá bude lepšia aj vždy v budúcnosti a tak tú prvú môžeme zahodiť.

Táto idea sa dá interpretovať aj kúsok inak: Pre každý unikátny znak si budeme pamätať minimálny počet krokov, ktoré potrebujeme na odstránenie reťazca končiaceho týmto písmenkom. Tieto hodnoty sa nám budú postupne pri prechádzaní reťazcom upravovať. Všimnime si, že tieto hodnoty určite nikdy neklesajú - keď už sme raz vedeli reťazec končiaci a zmazať \(k\) krokmi, tak aj akýkoľvek predĺžený reťazec končiaci a bude možné zmazať najviac \(k\) krokmi – proste len posledné zmazanie neukončíme na tom pôvodnom a, ale predĺžime ho až na nový koniec.

Na začiatku vieme len to, že prvé písmenko v reťazci vieme odstrániť jediným krokom. Následne, keď spracovávame ďalší znak, máme vždy dve možnosti:

1. Tento znak sme ešte nevideli. V tomto prípade ale nevieme urobiť nič iné, ako zmazať predošlý reťazec separátne a na tento jeden znak využiť krok navyše. Teda si preň uložíme hodnotu o \(1\) väčšiu ako predošlý znak v reťazci.
2. Znak sme už videli. Tu máme dve možnosti:

• Buď ho zmažeme separátne rovnako v prvom prípade
• Alebo len predĺžime zmazanie predošlého výskytu tohoto znaku ako sme popísali v predošlom odstavci.

Zložitosť

• Časová zložitosť: \(O(n)\), kde \(n\) je dĺžka vstupného reťazca.
• Pamäťová zložitosť: \(O(k)\), kde \(k\) je počet rôznych znakov v reťazci. To je pretože si potrebujeme pamätať minimálny počet krokov pre každý znak. Všimnime si, že reťazec spracovávame po jednom znaku, teda ho nepotrebujeme ukladať celý do pamäte.

s = input()

presolve = {s[0] : 1}

for i in range(1, len(s)):
    previous = s[i-1]
    current = s[i]

    if previous in presolve:
        if current not in presolve:
            presolve[current] = presolve[previous] + 1
        else:
            presolve[current] = min(presolve[previous] + 1, presolve[current])

print(presolve[s[-1]])

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>

int main() {
    std::string s;
    std::cin >> s;

    std::unordered_map<char, int> presolve;
    presolve[s[0]] = 1;

    for (size_t i = 1; i < s.size(); ++i) {
        char previous = s[i - 1];
        char current = s[i];

        if (presolve.count(previous)) {
            if (!presolve.count(current)) {
                presolve[current] = presolve[previous] + 1;
            } else {
                presolve[current] = std::min(presolve[previous] + 1, presolve[current]);
            }
        }
    }

    std::cout << presolve[s.back()] << std::endl;

    return 0;
}