Concepts Used
Strings, Hashing
Difficulty Level
Medium
Problem Statement (Simplified):
For given two string, Print minimum number of steps to make them anagram.
See original problem statement here
Test Case
Input:
1
expertcoder zenithcoder
Output:
4
Explanation:
In 'expertcoder' and 'zenithcoder', 7 characters ('e','t','c','o','d','e','r') are common in both.
Characters which are not common are :
In 'expertcoder' : 'e','x','p','r'
In 'zenithcoder' : 'z','n','i','h'
If we convert, 'e' to 'z', 'x' to 'n', 'p' to 'i' and 'r' to 'h', both strings becomes Anagram.
Solving Approach :
Anagram: Two strings are anagram if both of them contain the same characters with a different arrangement. For example prepbytes
and bytesprep
are anagrams.
-
We can count a minimum number of changes if we can find if how many numbers of characters are different in one string from another string. We do it for both of the strings.
-
We check this by scanning both strings, and increase value by
1
for the current character in 1st string and decrease the value by1
for the current character in 2nd string. -
After scanning both strings, we find the absolute sum of the hash table where
sum
represents the number of characters different in both strings. -
After checking this out, we know a single change would affect two characters, if we change one character to another one which is extra in second string and missing in the first string.
-
So we print half of that
sum
as our answer.
Example
- Lets assume two strings to be ‘
prepbuddy
‘ and ‘codepuddy
‘. - As we defined in the definition of anagram, two strings must have the same number of characters in any order. So we first find the number of characters which are different in both strings.
- We can calculate such characters using a hash table.
- After scanning both strings our hash table becomes
-
1
in hash table means character is present in 1st string but not in 2nd string, and-1
in hash table means character is present in 2nd string but not in 1st string,. -
Absolute sum of the hash table is
6
which means a total of6
characters are different, half of it i.e.3
is our final answer.
Solutions
#include <stdio.h> #include<string.h> int main() { int test; scanf("%d", &test); while(test--){ char a[100000], b[100000]; scanf("%s%s", a,b); int n = strlen(a); int hash[27] = {0}, count=0; for(int i=0; i<n; i++){ hash[a[i]-'a']++; hash[b[i]-'a']--; } for(int i=0; i<26; i++){ if(hash[i]<0) count -= hash[i]; } printf("%d\n", count); } }
#include <bits/stdc++.h> using namespace std; int main() { int test; cin>>test; while(test--){ string a, b; cin>>a>>b; int hash[26] = {0}, count=0; for(int i=0; i<b.length(); i++){ hash[a[i]-'a']++; hash[b[i]-'a']--; } for(int i=0; i<26; i++){ if(hash[i]<0) count -= hash[i]; } cout<<count<<endl; } }
import java.util.*; import java.io.*; import java.lang.Math; public class Main { public static void main(String args[]) throws IOException { Scanner sc= new Scanner(System.in); int test = sc.nextInt(); while(test != 0){ String a = sc.next(); String b = sc.next(); int hash[] = new int[26]; int count=0; for(int i=0; i<b.length(); i++){ hash[a.charAt(i)-'a']++; hash[b.charAt(i)-'a']--; } for(int i=0; i<26; i++){ if(hash[i]<0) count -= hash[i]; } System.out.println(count); test--; } }
for _ in range(int(input())): a, b = input().split() hash = [0] * 26 count = 0 for i in range(len(b)): hash[ord(a[i]) - ord("a")] += 1 hash[ord(b[i]) - ord("a")] -= 1 for i in range(26): if hash[i] < 0: count -= hash[i] print(count)
Space Complexity of this approach would be
O(1).
[forminator_quiz id="1285"]
This article tried to discuss the concept of Strings, Hashing. Hope this blog helps you understand and solve the problem. To practice more problems on Strings, Hashing you can check out MYCODE | Competitive Programming.