Subsequences of Length Two
Contest: Codeforces Round 667 (Div. 3)
Difficulty rating: 2100
Tags: dp, strings

You are given two strings $$$s$$$ and $$$t$$$ consisting of lowercase Latin letters. The length of $$$t$$$ is $$$2$$$ (i.e. this string consists only of two characters).

In one move, you can choose any character of $$$s$$$ and replace it with any lowercase Latin letter. More formally, you choose some $$$i$$$ and replace $$$s_i$$$ (the character at the position $$$i$$$) with some character from 'a' to 'z'.

You want to do no more than $$$k$$$ replacements in such a way that maximizes the number of occurrences of $$$t$$$ in $$$s$$$ as a subsequence.

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 200$$$; $$$0 \le k \le n$$$) — the length of $$$s$$$ and the maximum number of moves you can make. The second line of the input contains the string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters. The third line of the input contains the string $$$t$$$ consisting of two lowercase Latin letters.

Output format:
Print one integer — the maximum possible number of occurrences of $$$t$$$ in $$$s$$$ as a subsequence if you replace no more than $$$k$$$ characters in $$$s$$$ optimally.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, you can obtain the string "abab" replacing $$$s_1$$$ with 'a' and $$$s_4$$$ with 'b'. Then the answer is $$$3$$$.

In the second example, you can obtain the string "ssddsdd" and get the answer $$$10$$$.

In the fourth example, you can obtain the string "aaacaaa" and get the answer $$$15$$$.

Example input:
4 2
bbaa
ab

Example output:
3

Example input:
7 3
asddsaf
sd

Example output:
10

Editorial:
I'm almost sure this problem can be solved faster and with greater constraints but this version is fine for the last problem.
Consider both strings $$$0$$$-indexed and let's do the dynamic programming $$$dp_{i, j, cnt_0}$$$. It means the maximum number of occurrences of $$$t$$$ if we considered first $$$i$$$ characters of $$$s$$$, did $$$j$$$ moves and the number of characters $$$t_0$$$ is $$$cnt_0$$$. The answer to the problem is $$$\max\limits_{ck=0}^{k} \max\limits_{cnt_0=0}^{n} dp_{n, ck, cnt_0}$$$. Initially all states are $$$-\infty$$$ and $$$dp_{0, 0, 0}$$$ is $$$0$$$. What about transitions? There are essentially three types of them: don't change the current character, change the current character to $$$t_0$$$ and change the current character to $$$t_1$$$.
Let's create three additional variables to make our life easier (if that were true...). $$$e_0$$$ is $$$1$$$ if $$$s_i = t_0$$$ and $$$0$$$ otherwise, $$$e_1$$$ is $$$1$$$ if $$$s_i = t_1$$$ and $$$0$$$ otherwise and $$$e_{01}$$$ is $$$1$$$ if $$$t_0 = t_1$$$ and $$$0$$$ otherwise. Now let's make and describe our transitions:
• Don't change the $$$i$$$-th character:$$$dp_{i + 1, ck, cnt_0 + e_0} = max(dp_{i + 1, ck, cnt_0 + e_0}, dp_{i, ck, cnt_0} + (e_1~ ?~ cnt_0 : 0))$$$.The expression $$$x~ ?~ y : z$$$ is just ternary if statement: if $$$x$$$ is true, return $$$y$$$, otherwise return $$$z$$$. So, the number of characters $$$t_0$$$ increases if $$$s_i$$$ equals $$$t_0$$$ and the answer increases if the $$$i$$$-th character equals $$$t_1$$$ (because we added all occurrences that end in the $$$i$$$-th character).
• Change the $$$i$$$-th character to $$$t_0$$$ (possible only when $$$ck < k$$$):$$$dp_{i + 1, ck + 1, cnt_0 + 1} = max(dp_{i + 1, ck + 1, cnt_0 + 1}, dp_{i, ck, cnt_0} + (e_{01}~ ?~ cnt_0 : 0))$$$.The number of characters $$$t_0$$$ always increases and the answer increases if $$$t_0$$$ equals $$$t_1$$$ by the same reason as in the previous transition.
• Change the $$$i$$$-th character to $$$t_1$$$ (possible only when $$$ck < k$$$):$$$dp_{i + 1, ck + 1, cnt_0 + e_{01}} = max(dp_{i + 1, ck + 1, cnt_0 + e_{01}}, dp_{i, ck, cnt_0} + cnt_0)$$$.The number of characters $$$t_0$$$ increases only if $$$t_0 = t_1$$$ and the answer always increases.
Note that we always increase the number of moves in the second and the third transitions even when $$$s_i$$$ equals $$$t_0$$$ or $$$t_1$$$ because this case is handled in the first transition, so we don't care.
Time complexity: $$$O(n^3)$$$.
There are also some greedy approaches which work in $$$O(n^4)$$$ with pretty small constant and can be optimized even further.