HackerRank Anagram Problem Solution

In this post, we will solve HackerRank Anagram Problem Solution.

Two words are anagrams of one another if their letters can be rearranged to form the other word.
Given a string, split it into two contiguous substrings of equal length. Determine the minimum number of characters to change to make the two substrings into anagrams of one another.
Example
s = abccde
Break & into two parts: ‘abc’ and ‘cde’. Note that all letters have been used, the substrings are contiguous and their lengths are equal. Now you can change ‘a’ and ‘b’ in the first substring to ‘d’ and ‘e’ to have ‘dec’ and ‘cde’ which are anagrams. Two changes were necessary.

Function Description

Complete the anagram function in the editor below.

anagram has the following parameter(s):

string s: a string

Returns

int: the minimum number of characters to change or -1.

Input Format

The first line will contain an integer, q, the number of test cases.
Each test case will contain a string s.

Sample Input

6
aaabbb
ab
abc
mnop
xyyx
xaxbbbxx

Sample Output

Explanation
Test Case #01: We split s into two strings $1=’aaa’ and S2=’bbb’. We have to replace all three characters from the first string with ‘b’ to make the strings anagrams.
Test Case #02: You have to replace ‘a’ with ‘b’, which will generate “bb”.
Test Case #03: It is not possible for two strings of unequal length to be anagrams of one another.
Test Case #04: We have to replace both the characters of first string (“mn”) to make it an anagram of the other one.
Test Case #05: $1 and S2 are already anagrams of one another.
Test Case #06: Here S1 = “xaxb” and S2 = “bbxx”. You must replace ‘a’ from S1 with ‘b’ so that S1 = “xbxb”.

Table of Contents

Anagram C Solution

#include <stdio.h>
#include <string.h>
int main()
{
    int i,t;
    scanf("%d",&t);
    for(i=0;i<t;i++) {

       char str[10002];
       scanf("%s",str);
       int cnt,len = strlen(str);

       if(len % 2 == 0) {
            cnt = 0;
           char str1[10000] = {NULL};
           char str2[10000] = {NULL};
           strncpy(str1,str,len/2);
           strncpy(str2,str+len/2,len/2);
           mergeSort(str1,0,len/2-1);
           mergeSort(str2,0,len/2-1);
          // printf("%s %s\n",str1,str2);
           int m=0,n=0;

           while(m < len/2 && n < len/2) {
               if(str1[m] > str2[n]) n++;
               else if(str2[n] > str1[m]) m++;
               else {
                cnt++;
                n++;
                m++;
               }
            }
            printf("%d\n",len/2-cnt);
       }
       else printf("-1\n");
    }

    return 0;
}
void merge(char data[],int low,int high,int mid)
{
    int n = high - low +1;
    int temp[n], i=0, j=low, k=mid+1;
    while(j<=mid && k <=high)
    {
        if(data[j] <= data[k] )
            temp[i++] = data[j++];
        else
            temp[i++] = data[k++];
    }
    if(j>mid)
        while(k<=high) temp[i++] = data[k++];
    else if(k>high)
        while (j<=mid) temp[i++] = data[j++];
    for(i=0;i<n;i++)
        data[low+i] = temp[i];
    return;
}

void mergeSort(char list[],int low,int high)
{
    if(high <= low) return;
    else
    {
        int mid = (low + high)/2;
        mergeSort(list,low,mid);
        mergeSort(list,mid+1,high);
        merge(list,low,high,mid);
        return;
    }
}

Anagram C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;


int main() {
    unsigned int tt; cin>>tt;
    for (unsigned int t = 0; t<tt; ++t)
    {
        string str; cin>>str;
        if ((str.size()&1)==1)
        {
            cout<<-1<<'\n';
            continue;
        }
        int freq1[26]; fill(begin(freq1),end(freq1),0); 
        for (unsigned int i = 0; i<str.size()/2; ++i) ++freq1[str[i]-'a'];
        int freq2[26]; fill(begin(freq2),end(freq2),0);
        for (unsigned int i = str.size()/2; i<str.size(); ++i) ++freq2[str[i]-'a'];
        unsigned int counter = 0;
        for (unsigned int i = 0; i<26; ++i)
            counter += abs(freq2[i]-freq1[i]);
        cout<<counter/2<<'\n';
    }
    return 0;
}

Anagram C Sharp Solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Anagram {
    class Program {
        static void Main(string[] args) {
            int count = int.Parse(Console.ReadLine());
            for (int i = 0; i < count; i++) {
                string words = Console.ReadLine();
                if (words.Length % 2 == 1) {
                    Console.WriteLine(-1);
                }
                else {
                    string word1 = words.Substring(0, words.Length / 2);
                    string word2 = words.Substring(words.Length / 2);
                    Dictionary<char, int> map = new Dictionary<char, int>();
                    foreach (char c in word2) {
                        map[c] = map.ContainsKey(c) ? map[c] + 1 : 1;
                    }
                    foreach (char c in word1) {
                        map[c] = map.ContainsKey(c) ? map[c] - 1 : -1;
                    }

                    Console.WriteLine(map.Sum(x => Math.Max (x.Value , 0)));

                }
            }
        }
    }
}

Anagram Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'anagram' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts STRING s as parameter.
     */

    public static int anagram(String s) {
    // Write your code here
        if (s.length() % 2 == 1) {
            return -1;
        }
        var firstStr = s.substring(0, s.length()/2);
        var secondStr = s.substring(s.length()/2);
        var map = new HashMap<Character, Integer>();
        for (var i='a'; i<='z'; i++) {
            map.put(i, 0);
        }
        var set = new HashSet<Character>();
        for (var elem: secondStr.toCharArray()) {
            set.add(elem);
            var value = map.get(elem);
            map.put(elem, ++value);
        }
        for (var elem: firstStr.toCharArray()) {
            var value = map.get(elem);
            map.put(elem, --value);
        }

        var totalCount = 0;
        for (var elem: set) {
            var value = map.get(elem);
            totalCount += Math.max(0, value);
        }

        return totalCount;

    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, q).forEach(qItr -> {
            try {
                String s = bufferedReader.readLine();

                int result = Result.anagram(s);

                bufferedWriter.write(String.valueOf(result));
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Anagram JavaScript Solution

// Generated by CoffeeScript 1.8.0
var anagram, input, parse;

input = '';

anagram = function(s) {
  var a, b, end, key, letter, map_a, map_add, map_b, map_sub, start, sum, value, _i, _j, _len, _len1;
  end = Math.floor(s.length / 2);
  start = end;
  a = s.substr(0, end).split('').sort().join('');
  b = s.substr(start).split('').sort().join('');
  if (a === b) {
    return 0;
  }
  map_a = {};
  map_b = {};
  for (_i = 0, _len = a.length; _i < _len; _i++) {
    letter = a[_i];
    if (map_a[letter] == null) {
      map_a[letter] = 0;
    }
    map_a[letter]++;
  }
  for (_j = 0, _len1 = b.length; _j < _len1; _j++) {
    letter = b[_j];
    if (map_b[letter] == null) {
      map_b[letter] = 0;
    }
    map_b[letter]++;
  }
  map_add = {};
  map_sub = {};
  for (key in map_b) {
    value = map_b[key];
    if (map_a[key] !== value) {
      if (map_a[key] == null) {
        map_add[key] = value;
        continue;
      }
      if (map_a[key] < value) {
        map_add[key] = value - map_a[key];
      }
    }
  }
  sum = function(previous, key) {
    return map_add[key] + previous;
  };
  return Object.keys(map_add).reduce(sum, 0);
};

parse = function(rows) {
  var row, _i, _len, _results;
  _results = [];
  for (_i = 0, _len = rows.length; _i < _len; _i++) {
    row = rows[_i];
    if (row.length % 2 === 1) {
      console.log(-1);
      continue;
    }
    _results.push(console.log(anagram(row)));
  }
  return _results;
};

process.stdin.resume();

process.stdin.setEncoding('ascii');

process.stdin.on('end', function() {
  var row, rows;
  rows = input.split('\n');
  rows.shift();
  return parse((function() {
    var _i, _len, _results;
    _results = [];
    for (_i = 0, _len = rows.length; _i < _len; _i++) {
      row = rows[_i];
      if (row.length > 0) {
        _results.push(row);
      }
    }
    return _results;
  })());
});

process.stdin.on('data', function(chunk) {
  return input += chunk;
});

Anagram Python Solution

t = int(input())
for i in range(t):
  s = input().strip()
  if len(s) % 2 != 0:
    print(-1)
    continue
  a = s[:len(s)//2]
  b = s[len(s)//2:]
  cs = [0]*256
  for c in a:
    i = ord(c)
    cs[i] += 1
  for c in b:
    i = ord(c)
    cs[i] -= 1
  for i, e in enumerate(cs):
    cs[i] = abs(e)
  print(sum(cs)//2)