We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Strings
  4. Game of Thrones - I
  5. Discussions

Game of Thrones - I

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

Sort 920 Discussions, By:

votes

Please Login in order to post a comment

  • YaMogu
    7 years ago+ 36 comments

    If you are stuck you can follow this logic:

    If len(str) is even, count of each elemnt should be even.

    If len(str) is odd, count of ONLY one element should be odd, counts of all other elements should be even.

    177|
    Permalink
    View more Comments..
  • ganeshran
    7 years ago+ 5 comments

    But the Dothraki never cross the seas. How did they invade Westeros?

    I kid.. I kid

    29|
    Permalink
    View more Comments..
  • johnbanner
    5 years ago+ 2 comments

    bit shifting is fun :)

    int main() {
        string s;
        cin>>s;
    
        int flag = 0;
        uint64_t mask = 0x0;
        for (int i = 0; i < s.length(); i++)
            mask = mask ^ (1 << (s[i]-'a'));
        if ((!mask) || (((mask & (mask - 1)) == 0)))
            flag = 1;
        if(flag==0)
            cout<<"NO";
        else
            cout<<"YES";
        return 0;
    }
    
    13|
    Permalink
  • Alpha786
    2 years ago+ 0 comments

    C++ solution...

    string gameOfThrones(string s) {
    vector<int> f(26,0);
    for(int i=0;i<s.size();i++)
    {
        f[s[i]-'a']++;
    }
    int count1=0;
    for(int i=0;i<26;i++)
    {
        if(f[i]%2!=0&&count1==1)
        return "NO";
        if(f[i]%2!=0)
        count1++;
    }
    return "YES";
    }
    
    11|
    Permalink
  • dfoianu
    6 years ago+ 2 comments

    Here's a more in-depth explanation of the counting solution.

    The problem asks you to divide a string into two mirrored parts. For example:
    [abababab]
    [aabb][bbaa]

    A letter in the string can appear an odd or an even number of times. Let's consider what happens when the number of letters that appears an odd number of times varies.

    0 "odd letters":
    [aabbaabb]
    [----][----]
    Each letter on the left side must have a pair on the right side. If the number is even, it means we can definitely divide this string into two mirrored parts, as each letter does have a pair.

    1 "odd letters":
    [aabbaabbccc]
    [----]ccc[----]
    c[----]c[----]c
    When we have 1 "odd" letter, the string can only be a palindrome if the letter without a pair is in the middle, between the two mirrored parts. Therefore, we can make a palindrome in this case.

    2 or more "odd letters":
    [aabbaabbcccddd]
    [----]ccc[----]
    c[----]c[----]c
    In the case of one "odd" letter, we can put the unpaired one in the middle. But we only have one middle, so if the number of "odd" letters is any higher than 1, there is no possible position we can put the second "odd" letter and still have the string be a palindrome.

    11|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature