Showing posts with label Hackerrank. Show all posts
Showing posts with label Hackerrank. Show all posts

Wednesday, June 19, 2019

Make Anagrams, or, Remove duplicates

Intro:
This is a very basic question. I am writing about this just because I want to get into a habit of writing technical stuff. I am not so good at expressing my ideas and that is why I am starting out with such a simple example. I hope to start writing and keep on improving my writing skills. Any suggestion is welcome. 

Problem Statement:
There are two given strings. You have to find out the minimum number of character removals from each string so that both become anagrams.

Link to problem.

Thought Process:
The idea is to keep a count of all the characters in both the strings in two different arrays and then compare the counts. If there is a difference in count, the character has to be removed. Therefore, the difference needs to be added to the total count of characters to be removed.

Example:
String 1: abd
String 2: ace

Remove b & d from first string and c & e from second string and you have an anagram.
Total number of removals: 4

Code:

def makeAnagram(a, b):
    arr1 = [0] * 26
    arr2 = [0] * 26

    for c in a:
        arr1[ord(c) - ord('a')] += 1
    for c in b:
        arr2[ord(c) - ord('a')] += 1
    count = 0
    for i in range(26):
        diff = arr1[i] - arr2[i]
        if diff < 0:
            diff *= -1
        count += diff
    return count

Share: