def makeCombi(n, k):
ans = []
tmp = []
def makeCombiUtil(n, left, k):
if (k == 0):
ans.append(tmp[:])
return
for i in range(left, n + 1):
tmp.append(i)
makeCombiUtil(n, i + 1, k - 1)
tmp.pop()
makeCombiUtil(n, 1, k)
return ans
def fun(cmb, arr, b, s):
sum = 0
tempArr = []
for i in cmb:
tempArr.append(s[i-1])
l = 0
for i in range(len(arr)):
if arr[i] == b[i] or arr[i] in tempArr:
l += 1
else:
sum += (l * (l+1)) // 2
l = 0
return sum + (l * (l+1)) // 2
def f(n, k, a, b):
s = set()
for i in range(n):
if a[i] != b[i]:
s.add(a[i])
s = list(s)
if len(s) <= k:
return (n * (n + 1)) // 2
combArr = makeCombi(len(s), k)
mxm = 0
for cmb in combArr:
mxm = max(mxm, fun(cmb, a, b, s))
return mxm
for _ in range(int(input())):
n, k = map(int, input().split())
a = input().strip()
b = input().strip()
print(f(n, k, a, b))
#include <bits/stdc++.h>
#define forr(i,a,b) for(int i=(a);i<(b);i++)
#define forn(i,n) forr(i,0,n)
#define dforn(i,n) for(int i=n-1;i>=0;i--)
#define forall(it,v) for(auto it=v.begin();it!=v.end();it++)
#define sz(c) ((int)c.size())
#define rsz resize
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fst first
#define snd second
#ifdef ANARAP
//local
#else
//judge
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
map<char,int> m;
string a,b;
int n,k;
const int inf = 1e7;
int main() {
#ifdef NANO
freopen("input.in", "r", stdin);
//freopen("output.out","w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--){
cin>>n>>k;
cin>>a>>b;
set <char> aux;
for(auto e: a) aux.insert(e);
int id = 0;
m.clear();
for(auto e: aux) m[e] = id, id++;
long long ans = 0;
for(int mask = 0; mask<(1<<((int) aux.size()+1)); mask++){
if(__builtin_popcount(mask) <= k){
long long l = 0;
long long auxx = 0;
forn(i,n){
int idx = m[a[i]];
if(a[i] == b[i] or ((1<<idx)&mask)){
auxx += (i-l+1);
}
else l = i+1;
}
ans = max(ans,auxx);
}
}
cout<<ans<<'\n';
}
return 0;
}
590. N-ary Tree Postorder Traversal | 589. N-ary Tree Preorder Traversal |
1299. Replace Elements with Greatest Element on Right Side | 1768. Merge Strings Alternately |
561. Array Partition I | 1374. Generate a String With Characters That Have Odd Counts |
1822. Sign of the Product of an Array | 1464. Maximum Product of Two Elements in an Array |
1323. Maximum 69 Number | 832. Flipping an Image |
1295. Find Numbers with Even Number of Digits | 1704. Determine if String Halves Are Alike |
1732. Find the Highest Altitude | 709. To Lower Case |
1688. Count of Matches in Tournament | 1684. Count the Number of Consistent Strings |
1588. Sum of All Odd Length Subarrays | 1662. Check If Two String Arrays are Equivalent |
1832. Check if the Sentence Is Pangram | 1678. Goal Parser Interpretation |
1389. Create Target Array in the Given Order | 1313. Decompress Run-Length Encoded List |
1281. Subtract the Product and Sum of Digits of an Integer | 1342. Number of Steps to Reduce a Number to Zero |
1528. Shuffle String | 1365. How Many Numbers Are Smaller Than the Current Number |
771. Jewels and Stones | 1512. Number of Good Pairs |
672. Richest Customer Wealth | 1470. Shuffle the Array |