#179Programare

Cea mai lungă secvență de litere ordonate alfabetic

Enunț

Se citește de la tastatură un șir de cel mult 255 litere mici ale alfabetului englez. Să se găsească cea mai lungă secvență de caractere introduse consecutiv în care literele să fie ordonate alfabetic.

Dacă se citește șirul sybegifcabfayewfa se va afișa:

begi

Enunțul nu precizează ce se întâmplă la litere egale alăturate și nici care secvență se alege dacă există mai multe de lungime maximă. Rezolvarea de mai jos tratează literele egale ca fiind în ordine (aab e o secvență ordonată) și afișează prima secvență de lungime maximă. Ambele convenții se menționează explicit în lucrare.

Rezolvare

C++

#include <iostream>
using namespace std;

char s[300];

int main() {
    cin.getline(s, 300);

    int n = 0;
    while (s[n]) n++;
    if (n == 0) return 0;

    int start = 0, lung = 1;                // cea mai buna secventa de pana acum
    int i = 0;
    while (i < n) {
        int j = i;
        while (j + 1 < n && s[j + 1] >= s[j]) j++;   // se extinde cat timp nu scade
        if (j - i + 1 > lung) { lung = j - i + 1; start = i; }
        i = j + 1;                          // urmatoarea secventa incepe dupa cea curenta
    }

    for (int k = start; k < start + lung; k++) cout << s[k];
    cout << "\n";
    return 0;
}

Cum funcționează

Ăsta e tiparul de secvență maximală: șirul se sparge în bucăți care respectă o proprietate, și se reține cea mai lungă. Apare peste tot — cea mai lungă secvență crescătoare de numere, cel mai lung șir de caractere identice, cea mai lungă perioadă fără zile ploioase.

Ideea centrală: fiecare poziție aparține exact unei secvențe, deci nu e nevoie să încerci toate începuturile și toate sfârșiturile. Pornești de la i, extinzi cât poți spre dreapta, compari cu cea mai bună de până atunci, apoi sari direct după capătul găsit:

i = 0
cat timp i < n:
    extinde j de la i cat timp s[j+1] >= s[j]
    daca secventa [i..j] e mai lunga decat cea mai buna: retine-o
    i = j + 1        <- SARI, nu i++

i = j + 1 e detaliul care face algoritmul rapid. Cu i++ ai relua din interiorul unei secvențe deja analizate și ai face aceeași muncă de mai multe ori.

Literele fiind caractere, comparația s[j + 1] >= s[j] compară de fapt codurile lor ASCII. Pentru literele mici ale alfabetului englez, ordinea codurilor coincide cu ordinea alfabetică, deci comparația funcționează direct — fără conversii, fără funcții speciale.

Se reține poziția de start și lungimea, nu secvența copiată. E mai simplu, mai rapid, și nu riști să depășești un vector auxiliar.

Verificare pe exemplu: sybegifcabfayewfa se sparge în sy, begi, f, c, abf, ay, ew, f, a. Cea mai lungă e begi, cu 4 litere.

Greșeli frecvente

i++ în loc de i = j + 1 — răspunsul rămâne corect, dar algoritmul devine pătratic degeaba.
Reținerea doar a lungimii, fără poziția de start — la final știi cât e de lungă, dar nu ai ce afișa.
lung = 0 la inițializare pe un șir nevid — orice secvență de o literă e deja mai bună, deci merge; dar start rămâne neinițializat dacă uiți și cazul n == 0.
cin >> s în loc de getline — se oprește la primul spațiu. Aici enunțul spune doar litere, dar obiceiul te costă la problemele cu text.
> în loc de >= — literele egale alăturate rup secvența. Alege o convenție și scrie-o în lucrare; enunțul nu o precizează.

Apariții

Galati 2026 — problema 19 · sursa oficială