String Problem

1

Please help:

There is no editorial for this problem.
Edit: ab string | Practice Problems
The first link has some problem in statement. Thanks to @carre
@everule1 @ssjgz @carre
Thanks

2

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

3

Posted one more link for the same problem.

4

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[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
5

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)

6

Yes, it got AC, Please explain the approach.

7

done!

8

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

9

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’