Alternating Characters

See the original problem on HackerRank.

Solutions

This problem can be solved by counting the number of equal adjacent characters:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

size_t T;
cin >> T;
string s;
while (T--)
{
    cin >> s;
    auto cnt = 0;
    for (auto i=1; i<s.size(); ++i)
    {
        if (s[i]==s[i-1])
            cnt++;
    }
    cout << cnt << "\n";
}

This is an application of zip | map | reduce pattern:

1
2

cin >> s;
cout << inner_product(begin(s), end(s)-1, next(begin(s)), 0, plus<int>(), equal_to<char>()) << "\n";

We have the opportunity to play with the standard library. For example, if we erase all the adjacent equal characters, the answer is given by the difference between the original length of the string and the length of the new string:

1
2
3
4

cin >> s;
auto size = s.size();
s.erase(unique(begin(s), end(s)), end(s));
cout << size - s.size() << endl;

Another similar solution does not erase anything, instead it only counts the number of rearranged characters:

1
2

cin >> s;
cout << distance(unique(begin(s), end(s)), end(s)) << endl;

Although the last two solutions modify the string, they gave us the opportunity to learn how to erase all the adjacent equal characters from a string and also to see what unique really does.

A simple solution in Haskell is using the group function to split the string in groups of the same character and subtract the number of groups from the length of the string.

1
2
3
4
5

import Data.List

solve xs = ( length xs ) - ( length ( group xs ) )

main = interact $ unlines . fmap (show . solve) . tail . lines

Or you can count the number of equal adjacent characters:

1

solve xs = length $ filter ( \(l,r) -> l == r ) $ zip xs $ drop 1 xs

Make it shorter with zipWith:

1

solve xs = length . filter id $ zipWith (==) xs ( drop 1 xs )

With foldl:

1

solve xs = foldl ( \c (l, r) -> c + ( fromEnum ( l == r) ) ) 0 $ zip xs $ drop 1 xs