# PBinfo #1413 – ConstructPalindrom – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Marc

## Enunț

Mai sunt câteva săptămâni și vine Crăciunul. Ajuns într-un magazin de jucării, Robert îl roagă pe tatăl său să-i cumpere cea mai frumoasă mașină cu telecomandă. Tatăl său îi spune că nu a fost cuminte în timpul anului și nu merită această jucărie, însă după dispute intense acesta hotaraste să-i mai acorde o sansă, doar dacă va rezolva următoarea problema: 

Având un string S, putem să obținem un palindrom din acest șir ștergând un singur caracter? 

Robert nu se prea descurca la algoritmică așa că vă roagă foarte mult să-i rezolvați problema pentru a se putea juca cu mașina cu telecomandă. În schimbul acestei mașini el vă va recompensa cu 100 puncte.

Cerința
Find dat un string S, se poate obține un palindrom din șirul inițial ștergând doar un singur caracter ?

Date de intrare
Fişierul de intrare constructpalindrom.in conţine pe prima linie o valoare T reprezentând numărul de teste. Pe următoarele T linii vom avea cate un string reprezentând întrebarea adresata lui Robert de către tatăl sau.

Date de ieșire
Fişierul de ieşire constructpalindrom.out va conține T linii cu răspunsul YES daca se poate obține un palindrom ștergând un singur caracter și NO dacă nu se poate obține.

Restricții și precizări

1 <= T <= 100
Dimensiunea stringului <= 100000
Pentru 10% din punctaj dimensiunea stringului <= 1000
String-ul conține caractere de la a la z.
Dimensiunea string-ului după ștergerea unui caracter va fi mai mică decât a fost înainte.

Exemplu:
constructpalindrom.in

4
aaa
abc
abdbca
abba
constructpalindrom.out

YES
NO
YES
YES
Explicație
Pentru primul exemplu (aaa): Putem șterge orice a, string-ul rezultat este aa, care este palindrom.

Pentru al doilea exemplu (abc): Nu este posibil să eliminăm exact un caracter și să obtinem un palindrom.

Pentru al treilea exemplu (abdbca): ștergem caracterul c, string-ul rezultat este abdba care este palindrom.

Pentru exemplul al patrulea (abba): Ștergem b, obținem aba care este palindrom.

## Cod sursă C++

```cpp
#include <fstream>
#include <cstring>
using namespace std;
int main() {
  ifstream in("constructpalindrom.in");
  ofstream out("constructpalindrom.out");
  int t;
  char s[100001];
  in >> t;
  while(t--) {
    in >> s;
    int l = strlen(s), cnt = 0;
    for(int i = 0, j = l - 1; cnt < 2 && i <= j; ++i, --j) {
      if(s[i] != s[j])++cnt, --j;
      if(s[i] != s[j])--i, ++j;
    }
    if(cnt < 2) out << "YES\n";
    else out << "NO\n";
  }
  return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1413)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1413/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1413/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)