Flexible String (Codeforces 1778C)
Tags: Others, 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: 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: For each test case, print a single integer in a line, the maximum number of pairs $$$(l, r)$$$ satisfying the constraints.

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:   $$$a[1,1] = b[1,1] =$$$ "$$$\tt{a}$$$",  $$$a[1,2] = b[1,2] =$$$ "$$$\tt{ab}$$$",  $$$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.

Sample Inputs:
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

Sample Outputs:
6
3
6
6
6
11

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    a = input().strip()
    a = [ord(a[i]) - ord('a') for i in range(n)]
    b = input().strip()
    b = [ord(b[i]) - ord('a') for i in range(n)]
    letters = set(a)
    letters = list(letters)
    k = min(k, len(letters))
    ans = 0
    for msk in range(1 << len(letters)):
        cnt = 0
        for j in range(len(letters)):
            if msk >> j & 1:
                cnt += 1
        if cnt == k:
            change = [0] * 26
            for j in range(len(letters)):
                if msk >> j & 1:
                    change[letters[j]] += 1
            tot = 0
            before = 1
            for i in range(n):
                if a[i] == b[i] or change[a[i]]:
                    tot += before
                    before += 1
                else:
                    before = 1
            ans = max(ans, tot)
    print(ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def popcount(x):
    x = (x & 21845) + (x >> 1 & 21845)
    x = (x & 13107) + (x >> 2 & 13107)
    x = (x & 3855) + (x >> 4 & 3855)
    x = (x & 255) + (x >> 8 & 255)
    return x
t = int(input())
ans = []
pow2 = [1]
for _ in range(10):
    pow2.append(2 * pow2[-1])
cnt = [popcount(i) for i in range(pow2[10])]
for _ in range(t):
    (n, k) = map(int, input().split())
    a = list(input().rstrip())
    b = list(input().rstrip())
    u = [-1] * 26
    m = 0
    for i in a:
        if u[i - 97] == -1:
            u[i - 97] = m
            m += 1
    dp = [0] * pow2[m]
    c = [0] * pow2[m]
    x = []
    for i in range(pow2[m]):
        if cnt[i] <= k:
            x.append(i)
    for (i, j) in zip(a, b):
        v = u[i - 97]
        if i ^ j:
            p = pow2[v]
            for l in x:
                if not l & p:
                    c[l] = -1
                c[l] += 1
                dp[l] += c[l]
        else:
            for l in x:
                c[l] += 1
                dp[l] += c[l]
    ans0 = max(dp)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
from itertools import combinations
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))

def C2(n):
    return n * (n + 1) // 2

def solve():
    (n, k) = rl()
    a = input()
    b = input()
    bits = {}
    nxt = 1
    order = []
    for c in a:
        if c not in bits:
            bits[c] = nxt
            nxt *= 2
            order.append(c)
    fullmask = nxt - 1
    if k >= len(order):
        print(C2(n))
        return
    ans = 0
    for indices in combinations(range(len(order)), k):
        good = set()
        for i in indices:
            good.add(order[i])
        run = 0
        here = 0
        for i in range(n):
            if a[i] == b[i] or a[i] in good:
                run += 1
            else:
                here += C2(run)
                run = 0
        here += C2(run)
        ans = max(ans, here)
    print(ans)
mode = 'T'
if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()