Equal Strings Solution Codechef

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 iS.

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 become cb.
  • In the second operation, we can choose S={2} and αd. After this operation, A will become cd.

Test case 2:

  • In the first operation, we can choose S={1,3} and αb. After this operation, A will become bab.

Test case 3:

  • In the first operation, we can choose S={2,3} and αa. After this operation, A will become aaad.
  • In the second operation, we can choose S={4} and αb. After this operation, A will become aaab.

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:

Leave a Comment

7 + 17 =