# PBinfo #3638 – String Streak – Rezolvare C++

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

## Enunț

Cerința
Combatanții ezoterici au ajuns intr-o nouă lume, o lume plină de probleme ce pot fi o provocare până și pentru cei mai puternici concurenți.

Pentru prima provocare, combatanții v-au oferit un string ce conține litere mici ale alfabetului(în care se pot modifica litere) și un număr întreg n.

După ce s-au efectuat toate modificările, putem calcula costul după cum urmează: Dacă considerăm pozițiile modificate cu 1 și cele nemodificate cu 0, aflăm toate subsecvențele de 1 ce nu mai pot fi extinse la stânga sau dreapta, iar apoi pentru fiecare subsecvență, dacă intervalul modificat este [L, R], costul modificării va fi \({2}^{R-L+1}\).

De exemplu, dacă modificăm literele de pe pozițiile 1, 2, 4, 5 și 6, costul modificării literelor va fi 4 + 8 = 12(avem două subsecvențe de lungime 2 și 3).

Avem la dispoziție cel mult n euro și vrem să modificăm litere astfel încât să avem o subsecvență de lungime maximă care să conțină aceeași literă.

Date de intrare
Programul citește de la tastatură pe prima linie stringul s, iar pe cea de-a doua linie numărul n.

Date de ieșire
Programul va afișa pe ecran numărul S, reprezentând lungimea subsecvenței căutate.

Restricții și precizări

1 ≤ |s| ≤ 100000
1 ≤ n ≤ 1000000000
Pentru teste în valoare de 30 de puncte, 1 ≤ |s| ≤ 100

Exemplu:
Intrare

xabaabxab
10
Ieșire

9
Explicație
Se pot modifica literele de pe pozițiile 1, 3, 6, 7 și 9 pentru a obține 9 litere a la rând, cu costul de 10 euro.

## Cod sursă C++

```cpp
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
// #define fisier 1
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const double eps = 1e-9;
string s;
int n, L;
int nxt[100002][27];
int frq[32];
ll cost;
int ans;
int main()
{
	#ifdef fisier
		ifstream cin("input.in");
		ofstream cout("output.out");
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> s;
	L = s.size();
	s = ' ' + s;
	for(char lit = 'a'; lit <= 'z'; ++lit)
	{
		nxt[L+1][lit - 'a'] = L+1;
		for(int i = L; i >= 1; --i)
		{
			if(s[i] == lit)
				nxt[i][lit - 'a'] = i;
			else
				nxt[i][lit - 'a'] = nxt[i+1][lit - 'a'];
		}
	}
	cin >> n;
	for(char lit = 'a'; lit <= 'z'; ++lit)
	{
		memset(frq, 0, sizeof(frq));
		cost = 0;
		int Rp = 1;
		int str = 0;
		for(int i = 1; i <= L; ++i)
		{
			str = min(str, Rp - i);
			while(Rp <= L && cost <= n)
			{
				if(s[Rp] == lit)
				{
					str = 0;
				}
				else
				{
					++str;
					frq[str]++;
					if(str == 1) 
						cost += 1;
					cost += (1LL<<(str-1));
				}
				++Rp;
				if(cost <= n)
					ans = max(ans, Rp - i);
			}
			if(s[i] != lit)
			{
				int nxtp = min(Rp - i, nxt[i][lit - 'a'] - i);
				cost -= (1LL<<(nxtp-1));
                if (nxtp == 1) 
					cost--;
				frq[nxtp]--;
			}
			if(cost <= n)
				ans = max(ans, Rp - i - 1);
		}
	}
	cout << ans;
	return 0;
}
```

## Resurse

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