Game of Thrones

See the original problem on HackerRank.

Solutions

A palindrome string is one which has every char appearing in pairs except, eventually, one in the middle. So we can just count all the occurrences and check if the string has only one (or zero) odd occurrence.

A C++ Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() 
{
    int occ[26] = {};
    string s;
    cin>>s;
    
    for (auto i : s)
        ++occ[i-'a'];
    
    const auto odd = count_if(begin(occ), end(occ), [](int i {
          return i%2!=0;}
    );
    const auto flag = odd<=1;
    cout << (flag ? "YES" : "NO");
}

A PHP solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
<?php
function gameOfThrones($s) {
  $cnt = count_chars($s, 1);
  $odds = 0;
  foreach ($cnt as $c) {
    $odds += $c % 2;
    if ($odds > 1) {
      return "NO";
    }
  }
  return "YES";
}

Another (more functional) PHP solution:

1
2
3
4
<?php
function gameOfThrones($s) {
  return (count(array_filter(count_chars($s, 1), function($v) { return $v & 1;})) <= 1) ? "YES" : "NO" ;
}

An Haskell solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
import Data.List (sort, group)

gameOfThrones :: String -> Bool
gameOfThrones str = length (filter odd equals) <= 1
  where
    sorted = sort str
    equals = length <$> group sorted

yesNo True = "YES"
yesNo False = "NO"

main = getLine >>= putStr . yesNo . gameOfThrones

Pointfree style (function composition):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import Data.List (sort, group)

yesNo True = "YES"
yesNo False = "NO"

main = getLine >>= putStr
  . yesNo
  . (<= 1)
  . length
  . filter odd
  . map length
  . group
  . sort

Explanation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
[A,B,C,B,A]
sort
[A,A,B,B,C]
group
[[A,A],[B,B],[C]]
map length
[2,2,1]
filter odd
[1]
length
1

in C# by Lorenzo Rossoni

1
2
3
static string gameOfThrones(string s) {
  return s.ToCharArray().GroupBy(c => c).Count(cs => (cs.Count() % 2) != 0) <= 1 ? "YES" : "NO";
}

in Scala by Michele Mauro

1
2
3
4
5
def gameOfThrones(s: String): String = {
  val a= s.groupBy(c => c).mapValues(_.length)
  val odd= a.count(t => t._2 % 2 ==1)
  if (odd<=1) { "YES" } else { "NO" }
}
We've worked on this challenge in these gyms: modena  padua 
comments powered by Disqus