Question

Hash Tables C++

Bob and Carl both have words. Bob has a word S and Carl has a word T. They want to make both words S and T into anagrams of each other. Carl can apply two operations to convert word T to anagram of word S which are given below:

1.) Delete one character from the word T.

2.) Add one character from the word S.

Carl can apply above both operation as many times he wants. Find the minimum number of operations required to convert word T so that both T and S will be anagrams of each other.

Input:

First line of input contains number of test cases T. Each test case contains two lines. First line contains string S and second line contains string T.

Output:

For each test case print the minimum number of operations required to convert string T to anagram of string S.

Sample Input

    4
    abc
    cba
    abd
    acb
    talentpad
    talepdapd
    code
    road

Output for sample input

    0
    2
    4
    4

Answer 1

Hello! Firsly lets understand the solution then you can find the code below with attached screenshot. Comments are also written within code. Try to read those also. It passes all your given question test cases. Try with other test cases too. Hope those will also be passed by this solution.

First step is to sort both the strings. Once both strings are sorted you can now find the LCS(longest common subsequence) this tells how many characters are similar in both strings. Now we want to delete not similar characters from 'T'. So we have to perform Length(T) - LCS(S,T) operations , this will delete all dissimilar characters from T. Now we have to copy all the disimilar characters from S to T. Thus we have to perform Length(S) - LCS(S,T) operations. Add both operations you will get the answer. Now you can copy the code , compile it and then run it according to question.

1. #include<bits/stdc++.h>   
2. using namespace std;   
3.   
4. int max(int a, int b);   
5.   
6. /* Returns length of LCS for string X and Y */  
7. int lcs( string X, string Y, int m, int n )   
8. {   
9.     int L[m + 1][n + 1];   
10.     int i, j;   
11.       
12.     /* Following steps build L[m+1][n+1] in  
13.     bottom up fashion. Note that L[i][j]  
14.     contains length of LCS of X[0..i-1]  
15.     and Y[0..j-1] */  
16.     for (i = 0; i <= m; i++)   
17.     {   
18.         for (j = 0; j <= n; j++)   
19.         {   
20.         if (i == 0 || j == 0)   
21.             L[i][j] = 0;   
22.       
23.         else if (X[i - 1] == Y[j - 1])   
24.             L[i][j] = L[i - 1][j - 1] + 1;   
25.       
26.         else  
27.             L[i][j] = max(L[i - 1][j], L[i][j - 1]);   
28.         }   
29.     }   
30.           
31.     /* L[m][n] contains length of LCS  
32.     for X[0..n-1] and Y[0..m-1] */  
33.     return L[m][n];   
34. }   
35.   
36. /* Utility function to get max of 2 integers */  
37. int max(int a, int b)   
38. {   
39.     return (a > b)? a : b;   
40. }   
41.   
42. // Driver Code   
43. int main()   
44. {  
45.   //Enter the number of test cases   
46.     int T;  
47.     cin>>T;  
48.   
49.     while(T--)  
50.     {  
51.     //Enter the string S and then String T    
52.     string s,t;  
53.     cin>>s>>t;  
54.       
55.       
56.     //Getting the length of both strings in m and n variable.  
57.     int m = s.length();   
58.     int n = t.length();   
59.       
60.   
61.     //sorting the strings for running the lCS  
62.     sort(s.begin(),s.end());  
63.     sort(t.begin(),t.end());  
64.       
65.     int l = lcs( s, t, m, n );  
66.       
67.     //output the final result  
68.     cout<<(n-l)+(m-l)<<"\n";  
69.       
70.     }  
71.     return 0;   
72. }