Subtask 1:

For ~n \leq 20~, we can simply check all possible subsequences. Then check if that string satisfies being a grafted string.

Complexity: ~O(2^n)~.

Subtask 2: We will set ~a[i] = s[i] - 65 \quad \forall i = 1 \to n~.

Let ~cnt(c, i, j)~ be the number of characters ~c~ appearing in the range ~[i,j]~. We can quickly calculate this using a prefix sum array.

Let ~dp[i][j]~ be the longest subsequence ending at ~j~ with the ending character being ~i~.

We will have the formula:

~dp[a[i]][i] = \max(dp[a[j]][j]) \quad \forall j~ such that ~cnt(a[i], j, i) >= a[i]~ and ~a[j] < a[i]~.

Complexity: ~O(n^2)~.

Subtask 3:

For this subtask, we do not need to iterate through ~j~; instead, we will use the result from ~j-1~. And to find the position ~x~ such that ~cnt(c,x,j) = c~, we can use a prefix sum array combined with binary search or we can use a queue data structure.

$$dp[i][j] = dp[i][j-1]$$ $$dp[a[i]][i] = \max(dp[x-1][j]) \quad \forall j < a[i]$$.

Complexity: ~O(n\times 26)~.

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

#define long long long

#define N 100005

int dp[27][N];

queue<int> q[27];

int main() {
    string s;
    cin >> s;

    s = " " + s;

    for(int i = 0;i < 27;i++)
        for(int j = 0;j < s.length();j++)
            dp[i][j] = 0;

    int res = 0;

    for(int i = 1;i < s.length();i++)
    {
        char c = s[i];
        int len = c - 'a' + 1;
        q[len].push(i);

        for(int j = 1;j <= 26;j++)
            dp[j][i] = dp[j][i-1];

        if(q[len].size() < len)
            continue;
        while(q[len].size() > len)
            q[len].pop();

        dp[len][i] = max(dp[len][i], len);
        int x = q[len].front();

        for(int j = 1;j < len;j++)
            dp[len][i] = max(dp[j][x-1] + len, dp[len][i]);

        res = max(res, dp[len][i]);
    }


    cout << res << endl;


    return 0;
}