Number of character Deletion Required to Make 2 String Anagrams

An Anagram is a special type of word or phrase where rearranging the letters will create a valid new word.

  • The longest anagram of a single word, which uses all 27 letters is hydroxydeoxycorticosterones and hydroxydesoxycorticosterone
  • Japan's former capital Kyoto and current capital Tokyo are anagrams of each other.
  • The special words whose anagram are Palindromes as well, ie when read in reverse order, it creates a new word are called semordnilap. For example, stressed and desserts.
  • In Harry potter book series, the main antagonist, Lord Voldemort's childhood name was Tom Marvolo Riddle which is an anagram of i am lord voldemort
  • The most expendable synthetic fiber Spandex is an anagram of expands.
  • The special words whose anagrams have Opposite meanings are called Antigrams For example, Santa is the word Satan.
  • The anagrams of eleven plus two is twelve plus one.

 awesome and wesome are anagram to each other if we delete the a from awesome, hence Number of character Deletion Required to Make awesome and wesome Anagrams are 1.

learn more about Anagrams

package org.wesome.dsalgo;

import java.util.HashMap;
import java.util.Map;

public class DeletionForAnagrams {
    public static int DeleteForAnagrams(String string1, String string2) {
        Map<Character, Integer> map = new HashMap<>();
        int count = 0;
//        add all character of string 1 into map with count.
        for (int i = 0; i < string1.length(); i++) {
            if (map.containsKey(string1.charAt(i))) {
                int cur = map.get(string1.charAt(i));
                map.put(string1.charAt(i), cur + 1);
            } else {
                map.put(string1.charAt(i), 1);
            }
        }
//        remove elements of string 2 from map.
        for (int i = 0; i < string2.length(); i++) {
            if (map.containsKey(string2.charAt(i))) {
                int cur = map.get(string2.charAt(i));
                if (cur == 1) {
                    map.remove(string2.charAt(i));
                } else {
                    map.put(string2.charAt(i), cur - 1);
                }
            }
//            if map doesn't contain key
            else {
                count++;
            }
        }
//        count all the remaining count of map
        count += map.values().stream().mapToInt(i -> i).sum();
        return count;
    }
}
package org.wesome.dsalgo;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class DeletionForAnagramsTest {
    @Test
    void deletionForAnagramsTest1() {
        String string1 = "awesome", string2 = "wesome";
        Assertions.assertEquals(1, DeletionForAnagrams.DeleteForAnagrams(string1, string2));
    }

    @Test
    void deletionForAnagramsTest2() {
        String string1 = "showman", string2 = "woman";
        Assertions.assertEquals(2, DeletionForAnagrams.DeleteForAnagrams(string1, string2));
    }
}
plugins {
    id 'java'
}

group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8

configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
}

repositories {
    mavenCentral()
}

dependencies {
    testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}

test {
    useJUnitPlatform()
}

 

follow us on