Anagram | HackerRank Solution | Anagram Algorithm

Problem

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 s 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.

HackerRank Problem Link

Input

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

Output

The minimum number of characters to change or -1.

Constraints

• 1 <= q <= 100
• 1 <= | s | <= 10000

Sample Input

6
aaabbb
ab
abc
mnop
xyyx
xaxbbbxx

Sample Output

3
1
-1
2
0
1

Explanation
Test Case #02: You have to replace ‘a’ with ‘b’, which will generate “bb”.

Code Implementation

//
//  main.cpp
//  Anagram
//
//  Created by Himanshu on 20/02/22.
//

#include <iostream>
#include <string>
#define CHAR_SIZE 27
using namespace std;

int main() {
    long ans;
    string s;
    int T;

    cin>>T;
    
    while (T--) {
        ans = 0;
        cin>>s;
        long n = s.size();
        
        if (n%2 != 0) {
            printf("-1\n");
        } else {

            long *hash1 = new long[CHAR_SIZE]();
            long *hash2 = new long[CHAR_SIZE]();
            
            for(int i=0; i<n/2; i++) {
                hash1[s[i] - 'a']++;
            }

            for(int i=(int)n/2; i<n; i++) {
                hash2[s[i] - 'a']++;
            }
            
            for(int i=0; i<27; i++) {
                if(hash2[i] > hash1[i]) {
                    ans += hash2[i] - hash1[i];
                }
            }

            printf("%ld\n",ans);
        }
    }
    
    return 0;
}

Time Complexity: O(n)