Algoritmul, pas cu pas
Problema are două straturi. Întâi întrebăm, pentru fiecare număr: câte cifre adăugăm la dreapta ca să devină palindrom? Acel răspuns e costul numărului. Abia apoi lucrăm doar cu costurile: la cerința 1 le adunăm, iar la cerința 2 căutăm cea mai lungă felie de poziții consecutive a căror sumă de costuri încape în bugetul .
Cheia e să nu te sperie cifrele „adăugate". Pentru că adăugăm numai la dreapta, numărul de start nu se mișcă — el rămâne mereu începutul (prefixul) rezultatului. Tot ce putem alege e ce punem după el. Întrebarea devine: de unde încolo e numărul deja simetric?