Flexible String
Contest: Codeforces Round 848 (Div. 2)
Difficulty rating: 1600
Tags: bitmasks, brute force, strings

You have a string $$$a$$$ and a string $$$b$$$. Both of the strings have length $$$n$$$. There are at most $$$10$$$ different characters in the string $$$a$$$. You also have a set $$$Q$$$. Initially, the set $$$Q$$$ is empty. You can apply the following operation on the string $$$a$$$ any number of times:

- Choose an index $$$i$$$ ($$$1\leq i \leq n$$$) and a lowercase English letter $$$c$$$. Add $$$a_i$$$ to the set $$$Q$$$ and then replace $$$a_i$$$ with $$$c$$$.

For example, Let the string $$$a$$$ be "$$$\tt{abecca}$$$". We can do the following operations:

- In the first operation, if you choose $$$i = 3$$$ and $$$c = \tt{x}$$$, the character $$$a_3 = \tt{e}$$$ will be added to the set $$$Q$$$. So, the set $$$Q$$$ will be $$$\{\tt{e}\}$$$, and the string $$$a$$$ will be "$$$\tt{ab\underline{x}cca}$$$".
- In the second operation, if you choose $$$i = 6$$$ and $$$c = \tt{s}$$$, the character $$$a_6 = \tt{a}$$$ will be added to the set $$$Q$$$. So, the set $$$Q$$$ will be $$$\{\tt{e}, \tt{a}\}$$$, and the string $$$a$$$ will be "$$$\tt{abxcc\underline{s}}$$$".

You can apply any number of operations on $$$a$$$, but in the end, the set $$$Q$$$ should contain at most $$$k$$$ different characters. Under this constraint, you have to maximize the number of integer pairs $$$(l, r)$$$ ($$$1\leq l\leq r \leq n$$$) such that $$$a[l,r] = b[l,r]$$$. Here, $$$s[l,r]$$$ means the substring of string $$$s$$$ starting at index $$$l$$$ (inclusively) and ending at index $$$r$$$ (inclusively).

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1\leq n \leq 10^5$$$, $$$0\leq k\leq 10$$$) — the length of the two strings and the limit on different characters in the set $$$Q$$$.

The second line contains the string $$$a$$$ of length $$$n$$$. There is at most $$$10$$$ different characters in the string $$$a$$$.

The last line contains the string $$$b$$$ of length $$$n$$$.

Both of the strings $$$a$$$ and $$$b$$$ contain only lowercase English letters. The sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output format:
For each test case, print a single integer in a line, the maximum number of pairs $$$(l, r)$$$ satisfying the constraints.

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

Note:
In the first case, we can select index $$$i = 3$$$ and replace it with character $$$c = \tt{d}$$$. All possible pairs $$$(l,r)$$$ will be valid.

In the second case, we can't perform any operation. The $$$3$$$ valid pairs $$$(l,r)$$$ are:

1. $$$a[1,1] = b[1,1] =$$$ "$$$\tt{a}$$$",
2. $$$a[1,2] = b[1,2] =$$$ "$$$\tt{ab}$$$",
3. $$$a[2,2] = b[2,2] =$$$ "$$$\tt{b}$$$".

In the third case, we can choose index $$$2$$$ and index $$$3$$$ and replace them with the characters $$$\tt{c}$$$ and $$$\tt{d}$$$ respectively. The final set $$$Q$$$ will be $$$\{\tt{b}\}$$$ having size $$$1$$$ that satisfies the value of $$$k$$$. All possible pairs $$$(l,r)$$$ will be valid.

Example input:
6
3 1
abc
abd
3 0
abc
abd
3 1
xbb
xcd
4 1
abcd
axcb
3 10
abc
abd
10 3
lkwhbahuqa
qoiujoncjb

Example output:
6
3
6
6
6
11

Editorial:
If we can replace all the characters of the string $$$a$$$, we can transform the string $$$a$$$ to the string $$$b$$$. So, replacing more characters is always beneficial. For a fixed string $$$a$$$ and another fixed string $$$b$$$, if the answer is $$$x_1$$$ for $$$k_1$$$ and $$$x_2$$$ for $$$k_2$$$ $$$(k_1 < k_2)$$$, it can be shown that $$$x_1 \leq x_2$$$ always satisfies.
That is to say, we can safely consider the size of the set $$$q$$$ to be the maximum limit $$$min(k, u)$$$ where $$$u$$$ is the number of unique characters in the string $$$a$$$. Now, we can generate all possible sets of characters having size $$$min(k, u)$$$. Obviously, we won't take the characters that are not present in the string $$$a$$$ because they have no effect on the answer. There are many ways to generate the sets, like backtracking, bitmasking, etc. If we can calculate the number of valid pairs $$$(l, r)$$$ for each set efficiently, the rest task will be just taking the maximum of them.
To calculate the number of pairs for each set efficiently, we can observe the fact that if $$$a[l,r]=b[l,r]$$$ is true, $$$a[p,q] = b[p,q]$$$ satisfies for any $$$l\leq p\leq q\leq r$$$. So, we will get $$$\frac{c\times (c+1)}{2}$$$ number of valid pairs from here where $$$c=r-l+1$$$. Now, we can start iterating from the beginning of the string $$$a$$$. We can say that $$$a_i$$$ matches $$$b_i$$$ if they are equal or $$$a_i$$$ exists in the currently generated set.
While iterating, when we are on the $$$j$$$th index, we need to find the rightmost index $$$r$$$ such that $$$a[j,r]=b[j,r]$$$ satisfies. Then we need to add the number of valid pairs in this range to the contribution of this set. After that, we need to set the value of $$$j$$$ to $$$r+1$$$ and repeat the steps again. The rest of the tasks are trivial.
Time complexity: In each test case, $$$\mathcal{O}(n\times \binom{u}{m})$$$, where $$$m=min(k,u)$$$