Anagram · Coding Gym

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)

occ :: String -> [Int]
occ 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)) (occ xs) (occ 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. Occurences 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
46



fn to_index(c: u8) -> usize {
    (c - b'a') as usize
}

fn count_occurrences(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_occ = count_occurrences(left);
    let right_occ = count_occurrences(right);

    left_occ
        .into_iter()
        .zip(right_occ)
        .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 occurrence 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 locc[26] = {};
  int rocc[26] = {};

  size_t const half = size / 2;

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

  int sum = 0;

  for (size_t i = 0; i < 26; ++i) {
    sum += abs(locc[i] - rocc[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;
}

An alternative solution, where the first half of the string increments occurrences, the other half decrement occurrences The solution is the sum of positive occurrences. Idea by Marco Bergamin

 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


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

  int occ[26] = {};

  size_t const half = size / 2;

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

  for (size_t i = half; i < size; ++i) {
    --occ[(size_t)string[i] - 'a'];
  }

  int sum = 0;

  for (size_t i = 0; i < 26; ++i) {
    sum += occ[i] > 0 ? occ[i] : 0;
  }

  return sum;
}

sort strings