 # String Problem

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)

Code
``````#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;

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 = (s == 'b');
dp = (s == 'a');
dp = dp = dp = dp = n;
for (int i = 1; i < n; ++i) {
int zero = abs(s[i] - 'a');
int one = 1 - zero;
dp[i][zero] = dp[i - 1][zero];
dp[i][zero] = min(dp[i - 1][zero], dp[i - 1][one]);
dp[i][zero] = min(dp[i - 1][zero], dp[i - 1][one]);
dp[i][one] = dp[i - 1][one] + 1;
dp[i][one] = dp[i - 1][one] + 1;
dp[i][one] = dp[i - 1][one] + 1;
}
cout << n - min(dp[n-1],dp[n-1]) << '\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’