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
Sample output:-
imkhnpqnhlvaxlmrsskbyyrhwfvgteubrelgubvdmrdmesfxkpykprunzpustowmvhupkqsyjxmnptkcilmzcinbzjwvxshubeln
wfnfdassvfugqjfuruwrdumdmvxpbjcxorettxmpcivurcolxmeagsdundjronoehtyaskpwumqmpgzmtdmbvsykxhblxspgnpgfzydukvizbhlwmaajuytrhxeepvmcltjmroibjsdkbqjnqjwmhsfopjvehhiuctgthrxqjaclqnyjwxxfpdueorkvaspdnywupvmy
No of characters deleted is 102
------------------------------------------------------
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
------------------------------------------------------
Aivivu đại lý vé máy bay, tham khảo
ReplyDeletevé máy bay đi Mỹ Vietnam Airline
đặt vé máy bay hà nội hồ chà minh
vé máy bay sà i gòn hà nội
vé máy bay đi đà lạt khứ hồi
giá vé máy bay đi quy nhơn
dịch vụ taxi sân bay nội bà i
combo hà nội đà lạt 4 ngà y 3 đêm