Please help:

There is no editorial for this problem.

Edit: https://www.hackerearth.com/problem/algorithm/ab-string-1-018a59e9/description/

The first link has some problem in statement. Thanks to @carre

@everule1 @ssjgz @carre

Thanks

Please help:

There is no editorial for this problem.

Edit: https://www.hackerearth.com/problem/algorithm/ab-string-1-018a59e9/description/

The first link has some problem in statement. Thanks to @carre

@everule1 @ssjgz @carre

Thanks

don’t think the statement is correct, I would understand it if the second pattern is b^i a^j b^k

Posted one more link for the same problem.

I don’t remember my hackearth user to try the solution, please check if this work and if it does I can explain what I’ve done

[UPDATE] Yes, I tried and worked.

dp[i][letter][seg] stores the minimum number of characters you need to delete if you consider up to the i index of the string, the i character of the string letter (0 for ‘a’ and 1 for ‘b’) and seg is one of the 3 segments of the pattern (the pattern has 3 segments)

The transition of the dp is easer to understand from the code (I think). Of course the answer is in the dp[n-1] (when all string has been considered) and seg=2 (when the pattern has been completed)

```
#include<bits/stdc++.h>
using namespace std;
void READ(bool _local){
ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef _DEBUG
if (_local)
freopen ("in.txt", "r", stdin);
#endif
}
int dp[1000001][2][3];
int main() {
READ(1);
int t;cin>>t;
ios_base::sync_with_stdio(false); cin.tie(0);
while(t--) {
string s;
cin >> s;
int n = s.size();
dp[0][0][0] = (s[0] == 'b');
dp[0][1][0] = (s[0] == 'a');
dp[0][0][1] = dp[0][0][2] = dp[0][1][1] = dp[0][1][2] = n;
for (int i = 1; i < n; ++i) {
int zero = abs(s[i] - 'a');
int one = 1 - zero;
dp[i][zero][0] = dp[i - 1][zero][0];
dp[i][zero][1] = min(dp[i - 1][zero][1], dp[i - 1][one][0]);
dp[i][zero][2] = min(dp[i - 1][zero][2], dp[i - 1][one][1]);
dp[i][one][0] = dp[i - 1][one][0] + 1;
dp[i][one][1] = dp[i - 1][one][1] + 1;
dp[i][one][2] = dp[i - 1][one][2] + 1;
}
cout << n - min(dp[n-1][0][2],dp[n-1][1][2]) << '\n';
}
}
```

1 Like

u can try this one, it passed all test cases-

(note that in the ab string problem, you need not take n as input whereas in pattern in strings problem, you need to take it as input)

Yes, it got AC, Please explain the approach.

done!

Can you tell the logic behind dp[i][one][0/1/2] ??

the state of dp[i][letter][seg] represents the minimun number of characters that you need to delete to get the state caracterized by:

- [i], indicates up to what index of the string we are considering (from 0 to n)
- [letter], indicates the last letter of the state (there are only 2 possibilities, 0 for ‘a’ and 1 for ‘b’)
- [seg]. this indicates what part of pattern we are considering. In more detail, consider the pattern a^i b^j a^k. It has 3 parts, a bounch of a's, then a bounch of b's and finally another bounch of a's. The last variable of dp, that is the one I called seg indicates which one of this 3 parts we are considering. Thas is why this variable can be 0, 1 or 2 (first,second and third part).

Don’t let the use of variables one and zero blind your understanding, they are there just to avoid the use of if's; the same can be done if you write alternative code to manage s[i]=‘a’ or s[i]=‘b’