Equal Strings Solution Codechef
Given a string A of length N consisting of lowercase English alphabet letters. You are allowed to perform the following operation on the string A any number of times:
- Select a non-empty subsequence S of the array [1,2,3,…,N] and any lowercase English alphabet α;
- Change Ai to α for all i∈S.
Find the minimum number of operations required to convert A into a given string B of length N consisting of lowercase English alphabet letters.
Input Format
- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follow.
- The first line of each test case contains an integer N – the length of the string A and B.
- The second line of each test case contains the string A.
- The third line of each test case contains the string B.
Output Format
For each test case, output the minimum number of operations required to convert string A into string B.
Constraints
- 1≤T≤104
- 1≤N≤105
- Sum of N over all test cases does not exceed 105.
Sample 1:
Input
3 2 ab cd 3 aaa bab 4 abcd aaab
Output
2 1 2
Explanation:
Test case 1:
- In the first operation, we can choose S={1} and α=
c
. After this operation, A will becomecb
. - In the second operation, we can choose S={2} and α=
d
. After this operation, A will becomecd
.
Test case 2:
- In the first operation, we can choose S={1,3} and α=
b
. After this operation, A will becomebab
.
Test case 3:
- In the first operation, we can choose S={2,3} and α=
a
. After this operation, A will becomeaaad
. - In the second operation, we can choose S={4} and α=
b
. After this operation, A will becomeaaab
.
SOLUTION
Program: Equal Strings Solution in Python
for _ in range(int(input())):
n=int(input())
s1=input()
s2=input()
res=[]
for j in range(n):
if s1[j]!=s2[j]:
res.append(s2[j])
print(len(set(res)))
Program: Equal Strings Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string a,b;
cin>>a>>b;
set<char> s;
for(int i=0;i<n;i++)
{
if(a[i]!=b[i])
{
s.insert(b[i]);
}
}
cout<<s.size()<<endl;
}
return 0;
}
Program: Equal Strings Solution in Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0)
{
int n = sc.nextInt();
String a = sc.next();
String b = sc.next();
Set<Character> set = new HashSet<>();
for(int i =0;i<n;i++)
{
if(a.charAt(i) != b.charAt(i))
set.add(b.charAt(i));
}
System.out.println(set.size());
}
}
}
Related: