Tuesday, 18 July 2017

Algorithms | Remove minimum number of characters so that two strings become anagram

There are two strings (both in lowercase), our task is to make them anagram.

Note: Only removal of the character is allowed from the Strings, find the minimum number of characters to be deleted to make both the strings anagram?
Examples are:
Input: string1 = "xyaweh" string2 = "hea"
Output: 3
We need to remove x, y and w from string.

Input: string1 = "cllgd" string2 = "gcd"
Output: 2

Input: string1 = "pqrs" string2 = "srpq"
Output: 0

MakeAnagram.java
package com.algorithm.forum.string;
public class MakeAnagram {
    
     /** Method to return required changes to make both the string anagram. */
     private static int makeAnagram(char[] str1, char[] str2) {

           int[] dpArray = new int[26];

           /** Count the occurrence of each character in the string1. */
           for (char key : str1) {
                int index = key - 'a';
                dpArray[index] = dpArray[index]+1;
           }
          
           /** Count down the occurrence of all character exist in string2. */
           for (char key : str2) {
                int index = key - 'a';
                dpArray[index] = dpArray[index]-1;
           }
          
           int changes = 0;
           /**
            *  Character need to deleted should be absolute some
            *  on extra character in string1 and string2.
            **/
           for (int value : dpArray) {
                changes = changes + Math.abs(value);
           }
           return changes;
     }
    
     /** Code Driver. */
     public static void main(String[] args) {
           String str1 = "geeksforeeks";
           String str2 = "geeksgeesfor";

           int count = makeAnagram(str1.toCharArray(), str2.toCharArray());

           System.out.println("Change required to make anagram "+ count);
     }
}

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...