Remove minimum number of characters so that two strings become anagram
Last Updated :
11 Sep, 2023
Given two strings in lowercase, the task is to make them anagram. The only allowed operation is to remove a character from any string. Find minimum number of characters to be deleted to make both the strings anagram?
If two strings contains same data set in any order then strings are called Anagrams.
Examples :
Input : str1 = "bcadeh" str2 = "hea"
Output: 3
We need to remove b, c and d from str1.
Input : str1 = "cddgk" str2 = "gcd"
Output: 2
Input : str1 = "bca" str2 = "acb"
Output: 0
The idea is to make character count arrays for both the strings and store frequency of each character. Now iterate the count arrays of both strings and difference in frequency of any character abs(count1[str1[i]-‘a’] – count2[str2[i]-‘a’]) in both the strings is the number of character to be removed in either string.
Implementation:
C++
#include<bits/stdc++.h>
using namespace std;
const int CHARS = 26;
int remAnagram(string str1, string str2)
{
int count1[CHARS] = {0}, count2[CHARS] = {0};
for (int i=0; str1[i]!='\0'; i++)
count1[str1[i]-'a']++;
for (int i=0; str2[i]!='\0'; i++)
count2[str2[i]-'a']++;
int result = 0;
for (int i=0; i<26; i++)
result += abs(count1[i] - count2[i]);
return result;
}
int main()
{
string str1 = "bcadeh", str2 = "hea";
cout << remAnagram(str1, str2);
return 0;
}
|
Java
import java.util.*;
class GFG {
static int remAnagram(String str1, String str2)
{
int count1[] = new int[26];
int count2[] = new int[26];
for (int i = 0; i < str1.length() ; i++)
count1[str1.charAt(i) -'a']++;
for (int i = 0; i < str2.length() ; i++)
count2[str2.charAt(i) -'a']++;
int result = 0;
for (int i = 0; i < 26; i++)
result += Math.abs(count1[i] -
count2[i]);
return result;
}
public static void main(String[] args)
{
String str1 = "bcadeh", str2 = "hea";
System.out.println(remAnagram(str1, str2));
}
}
|
Python3
CHARS = 26
def remAnagram(str1, str2):
count1 = [0]*CHARS
count2 = [0]*CHARS
i = 0
while i < len(str1):
count1[ord(str1[i])-ord('a')] += 1
i += 1
i =0
while i < len(str2):
count2[ord(str2[i])-ord('a')] += 1
i += 1
result = 0
for i in range(26):
result += abs(count1[i] - count2[i])
return result
if __name__ == "__main__":
str1 = "bcadeh"
str2 = "hea"
print(remAnagram(str1, str2))
|
C#
using System;
class GFG
{
static int remAnagram(string str1,
string str2)
{
int []count1 = new int[26];
int []count2 = new int[26];
for (int i = 0; i < str1.Length ; i++)
count1[str1[i] -'a']++;
for (int i = 0; i < str2.Length ; i++)
count2[str2[i] -'a']++;
int result = 0;
for (int i = 0; i < 26; i++)
result += Math.Abs(count1[i] -
count2[i]);
return result;
}
public static void Main()
{
string str1 = "bcadeh",
str2 = "hea";
Console.Write(remAnagram(str1, str2));
}
}
|
PHP
<?php
function remAnagram($str1, $str2)
{
$count1 = array(26);
$count2 = array(26);
for ($i = 0; $i < strlen($str1) ; $i++)
$count1[$str1[$i] - 'a']++;
for ($i = 0; $i < strlen($str2) ; $i++)
$count2[$str2[$i] -'a']++;
$result = 0;
for ($i = 0; $i < 26; $i++)
$result += abs($count1[$i] -
$count2[$i]);
return $result;
}
{
$str1 = "bcadeh"; $str2 = "hea";
echo(remAnagram($str1, $str2));
}
|
Javascript
<script>
function remAnagram(str1, str2)
{
var count1 = Array.from({length: 26}, (_, i) => 0);
var count2 = Array.from({length: 26}, (_, i) => 0);
for (i = 0; i < str1.length ; i++)
count1[str1.charAt(i).charCodeAt(0) -'a'.charCodeAt(0)]++;
for (i = 0; i < str2.length ; i++)
count2[str2.charAt(i).charCodeAt(0) -'a'.charCodeAt(0)]++;
var result = 0;
for (i = 0; i < 26; i++)
result += Math.abs(count1[i] -
count2[i]);
return result;
}
var str1 = "bcadeh", str2 = "hea";
document.write(remAnagram(str1, str2));
</script>
|
Time Complexity : O(n)
Auxiliary space : O(ALPHABET-SIZE)
The above solution can be optimized to work with single count array.
C++
#include <bits/stdc++.h>
using namespace std;
const int CHARS = 26;
int countDeletions(string str1, string str2)
{
int arr[CHARS] = {0};
for (int i = 0; i < str1.length(); i++)
arr[str1[i] - 'a']++;
for (int i = 0; i < str2.length(); i++)
arr[str2[i] - 'a']--;
long long int ans = 0;
for(int i = 0; i < CHARS; i++)
ans +=abs(arr[i]);
return ans;
}
int main() {
string str1 = "bcadeh", str2 = "hea";
cout << countDeletions(str1, str2);
return 0;
}
|
Java
class GFG {
final static int CHARS = 26;
static int countDeletions(String str1, String str2) {
int arr[] = new int[CHARS];
for (int i = 0; i < str1.length(); i++) {
arr[str1.charAt(i) - 'a']++;
}
for (int i = 0; i < str2.length(); i++) {
arr[str2.charAt(i) - 'a']--;
}
int ans = 0;
for (int i = 0; i < CHARS; i++) {
ans += Math.abs(arr[i]);
}
return ans;
}
static public void main(String[] args) {
String str1 = "bcadeh", str2 = "hea";
System.out.println(countDeletions(str1, str2));
}
}
|
Python3
def makeAnagram(a, b):
buffer = [0] * 26
for char in a:
buffer[ord(char) - ord('a')] += 1
for char in b:
buffer[ord(char) - ord('a')] -= 1
return sum(map(abs, buffer))
if __name__ == "__main__" :
str1 = "bcadeh"
str2 = "hea"
print(makeAnagram(str1, str2))
|
C#
using System;
public class GFG {
readonly static int CHARS = 26;
static int countDeletions(String str1, String str2) {
int []arr = new int[CHARS];
for (int i = 0; i < str1.Length; i++) {
arr[str1[i]- 'a']++;
}
for (int i = 0; i < str2.Length; i++) {
arr[str2[i] - 'a']--;
}
int ans = 0;
for (int i = 0; i < CHARS; i++) {
ans += Math.Abs(arr[i]);
}
return ans;
}
static public void Main() {
String str1 = "bcadeh", str2 = "hea";
Console.WriteLine(countDeletions(str1, str2));
}
}
|
PHP
<?php
function countDeletions($str1, $str2)
{
$CHARS = 26;
$arr = array();
for ($i = 0; $i < strlen($str1); $i++)
{
$arr[ord($str1[$i]) - ord('a')]++;
}
for ($i = 0; $i < strlen($str2); $i++)
{
$arr[ord($str2[$i]) - ord('a')]--;
}
$ans = 0;
for ($i = 0; $i < $CHARS; $i++)
{
$ans += abs($arr[$i]);
}
return $ans;
}
$str1 = "bcadeh"; $str2 = "hea";
echo(countDeletions($str1, $str2));
?>
|
Javascript
<script>
CHARS = 26;
function countDeletions(str1, str2)
{
var arr = Array.from({length: CHARS}, (_, i) => 0);
for(i = 0; i < str1.length; i++)
{
arr[str1.charAt(i).charCodeAt(0) -
'a'.charCodeAt(0)]++;
}
for(i = 0; i < str2.length; i++)
{
arr[str2.charAt(i).charCodeAt(0) -
'a'.charCodeAt(0)]--;
}
var ans = 0;
for(i = 0; i < CHARS; i++)
{
ans += Math.abs(arr[i]);
}
return ans;
}
str1 = "bcadeh", str2 = "hea";
document.write(countDeletions(str1, str2));
</script>
|
Time complexity: O(n) where n is the total number of characters in both strings.
Auxiliary space: O(1) as we only use a constant size array.
Thanks to vishal9619 for suggesting this optimized solution.
Another Approach: Using Counter from collections module
Explanation:
- The collections module provides a Counter class that works like a dictionary to count the frequency of elements in a list or string.
- The makeAnagram function takes two strings a and b as input.
- freq = Counter(a) initializes a counter object freq with the characters in string a.
- freq.subtract(Counter(b)) subtracts the characters in string b from the counter object. This operation will update the counts of the characters in freq.
- sum(abs(count) for count in freq.values()) calculates the sum of absolute values of counts in the counter object freq.
C++
#include <iostream>
#include <map>
#include <string>
using namespace std;
int makeAnagram(string a, string b)
{
map<char, int> freq;
for (char c : a) {
freq++;
}
for (char c : b) {
freq--;
}
int count = 0;
for (auto p : freq) {
count += abs(p.second);
}
return count;
}
int main()
{
string str1 = "bcadeh";
string str2 = "hea";
cout << makeAnagram(str1, str2) << endl;
return 0;
}
|
Java
import java.util.HashMap;
import java.util.Map;
public class Main {
public static int makeAnagram(String a, String b) {
Map<Character, Integer> freq = new HashMap<>();
for (char c : a.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
for (char c : b.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) - 1);
}
int count = 0;
for (int val : freq.values()) {
count += Math.abs(val);
}
return count;
}
public static void main(String[] args) {
String str1 = "bcadeh";
String str2 = "hea";
System.out.println(makeAnagram(str1, str2));
}
}
|
Python3
from collections import Counter
def makeAnagram(a, b):
freq = Counter(a)
freq.subtract(Counter(b))
return sum(abs(count) for count in freq.values())
if __name__ == "__main__":
str1 = "bcadeh"
str2 = "hea"
print(makeAnagram(str1, str2))
|
C#
using System;
using System.Collections.Generic;
namespace ConsoleApp {
class Program {
static int MakeAnagram(string a, string b)
{
Dictionary<char, int> freq
= new Dictionary<char, int>();
foreach(char c in a)
{
if (freq.ContainsKey(c)) {
freq++;
}
else {
freq.Add(c, 1);
}
}
foreach(char c in b)
{
if (freq.ContainsKey(c)) {
freq--;
}
else {
freq.Add(c, -1);
}
}
int count = 0;
foreach(KeyValuePair<char, int> p in freq)
{
count += Math.Abs(p.Value);
}
return count;
}
static void Main(string[] args)
{
string str1 = "bcadeh";
string str2 = "hea";
Console.WriteLine(MakeAnagram(str1, str2));
}
}
}
|
Javascript
function makeAnagram(string1, string2) {
let freq = new Map();
for (let c of string1) {
freq.set(c, (freq.get(c) || 0) + 1);
}
for (let c of string2) {
freq.set(c, (freq.get(c) || 0) - 1);
}
let count = 0;
for (let [key, value] of freq) {
count += Math.abs(value);
}
return count;
}
let str1 = "bcadeh";
let str2 = "hea";
console.log(makeAnagram(str1, str2));
|
Time complexity: O(len(a) + len(b))
The time complexity of the function is O(len(a) + len(b)), where len(a) and len(b) are the lengths of the input strings.
Auxiliary Space: O(len(a) + len(b))
The space complexity of the function is O(len(a) + len(b)). This is because the function creates a frequency buffer of length 26 to store the count of each character in the input strings
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...