Anagram

See the original problem on HackerRank.

Solutions

Possible C++ Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <set>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int T;
    cin >> T;
    string s;
    while (T--)
    {
        cin >> s;
        if (s.size() % 2)
        {
            cout << -1 << endl;
            continue;
        }
        multiset<char> inters;
        const auto splitIt = begin(s)+(s.size()/2);
        sort(begin(s), splitIt);
        sort(splitIt, end(s));
        set_intersection(begin(s), splitIt, splitIt, end(s), inserter(inters, end(inters)));
        cout << (s.size()/2-inters.size()) << endl;
    }
}

Haskell solution by Alessandro Pezzato. Strings with an odd number of letters do not have a solution. Strings are divided in two equal parts and we count occurrences for each letter. For each letter, we count the difference of occurrences. The sum divided by two is the solution.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import Data.List (group, sort, sortOn, zipWith)

freq :: String -> [Int]
freq str =
  fmap snd $
  sortOn fst $
  fmap (\cs -> (head cs, (length cs) - 1)) . group . sort $ ['a' .. 'z'] ++ str

countChanges :: (String, String) -> Int
countChanges (xs, ys) =
  div (sum $ zipWith (\x y -> abs (x - y)) (freq xs) (freq ys)) 2

split :: Int -> String -> (String, String)
split n str = (take n str, drop n str)

tryCountChanges :: String -> Int
tryCountChanges str =
  if odd n
    then -1
    else countChanges (split (n `div` 2) str)
  where
    n = length str

main = interact (unlines . fmap (show . tryCountChanges) . tail . lines)

Almost the same, but in Rust. Frequency table is a Vec<i32>, so it is updated in costant time, while scanning is done in linear time, without needing to sort.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
fn to_index(c: u8) -> usize {
    (c - b'a') as usize
}

fn count_frequencies(string: &str) -> Vec<i32> {
    let mut f = Vec::new();

    f.resize(to_index(b'z') + 1, 0);

    for c in string.as_bytes() {
        f[to_index(*c)] += 1;
    }

    f
}

fn count_changes(string: &str) -> i32 {
    if (string.len() & 1) == 1 {
        return -1;
    }

    let (left, right) = string.split_at(string.len() / 2);

    let left_freq = count_frequencies(left);
    let right_freq = count_frequencies(right);

    left_freq
        .into_iter()
        .zip(right_freq)
        .fold(0, |sum, (l, r)| sum + (l - r).abs())
        / 2
}

fn main() {
    use std::io::{self, BufRead};

    let stdin = io::stdin();

    let lines = stdin.lock().lines().map(Result::unwrap).skip(1);
    let results = lines.map(|string| count_changes(string.as_str()));

    for result in results {
        println!("{:}", result);
    }
}

And this is a C solution using array as frequency table. By Alessandro Pezzato

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <stdlib.h>

int count_changes(char* string, size_t size) {
  if (size & 1) {
    return -1;
  }

  int lfreq[26] = {};
  int rfreq[26] = {};

  size_t const half = size / 2;

  for (size_t i = 0; i < half; ++i) {
    ++lfreq[(size_t)string[i] - 'a'];
    ++rfreq[(size_t)string[i + half] - 'a'];
  }

  int sum = 0;

  for (size_t i = 0; i < 26; ++i) {
    sum += abs(lfreq[i] - rfreq[i]);
  }

  return sum / 2;
}

int main() {
  int n;
  scanf("%i\n", &n);
  char* string = malloc(10001 * sizeof(char));

  for (int i = 0; i < n; ++i) {
    size_t size = 10001;
    size = getline((char**)&string, &size, stdin);

    /* Fix strings ending with space or newline */
    while (string[size - 1] == ' ' || string[size - 1] == '\n') {
      size -= 1;
    }

    printf("%i\n", count_changes(string, size));
  }

  free(string);
  return 0;
}
We've worked on this challenge in these gyms: modena 
comments powered by Disqus