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)
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;
}
|