Aug 27, 2016

Minimum number of character deletions required to make two strings anagrams

Problem statement: Given two strings s1 and s2 such that, they may or may not be of the same length. Determine the minimum number of character deletions required to make s1 and s2 anagrams. Any characters can be deleted from either of the strings.
s1= qcvdb
s2= asbc
output : 5

Complete Sample program :-

import java.util.*;

public class MakeAnagram {
public static int numberNeeded(String first, String second) {
 char[] ch1 = first.toCharArray();
 char[] ch2 = second.toCharArray();
 int count = 0;
 Map<Character, Integer> map = new HashMap<Character, Integer>();
 for (int j = 0; j < ch2.length; j++) {
  char t = ch2[j];
  if (map.get(t) != null) {
   map.put(t, map.get(t) + 1);
  } else {
   map.put(t, 1);
  }
 }

 for (int j = 0; j < ch1.length; j++) {
  char t = ch1[j];
  if (map.get(t) != null) {
   if (map.get(t) != 0)
    map.put(t, map.get(t) - 1);
   else
    count++;
  } else {
   count++;
  }
 }
 int temp = 0;
 for (Character c : map.keySet()) {
  temp += map.get(c);
 }
 System.out.println(temp + " " + count);
 return temp + count;
}

public static void main(String[] args) {
 Scanner in = new Scanner(System.in);
 String input1 = in.next();
 String input2 = in.next();
 System.out.println("No of characters deleted is "+ numberNeeded(first, second));
}
}

Sample output
:-
imkhnpqnhlvaxlmrsskbyyrhwfvgteubrelgubvdmrdmesfxkpykprunzpustowmvhupkqsyjxmnptkcilmzcinbzjwvxshubeln

wfnfdassvfugqjfuruwrdumdmvxpbjcxorettxmpcivurcolxmeagsdundjronoehtyaskpwumqmpgzmtdmbvsykxhblxspgnpgfzydukvizbhlwmaajuytrhxeepvmcltjmroibjsdkbqjnqjwmhsfopjvehhiuctgthrxqjaclqnyjwxxfpdueorkvaspdnywupvmy

No of characters deleted is 102
------------------------------------------------------
Location: Hyderabad, Telangana, India