HackerRank Game of Thrones-CodePudding

I am trying to solve this problem on HackerRank and I am having a issue with my logic. I am confused and not able to think what I'm doing wrong, feels like I'm stuck in logic.

Question link: https://www.hackerrank.com/challenges/game-of-thrones/

I created a dictionary of alphabets with value 0. And then counting number of times the alphabet appears in the string. If there are more than 1 alphabet characters occurring 1 times in string, then obviously that string cannot become a palindrome. That's my logic, however it only pass 10/21 test cases.

Here's my code:

def gameOfThrones(s):
    alpha_dict = {chr(x): 0 for x in range(97,123)}
    counter = 0
    
    for i in s:
        if i in alpha_dict:
            alpha_dict[i]  = 1
            
    for key in alpha_dict.values():
        if key == 1:
            counter  = 1
    
    if counter <= 1:
        return 'YES'
    else:
       return 'NO'

Any idea where I'm going wrong?

CodePudding user response：

Explanation

The issue is that the code doesn't really look for palindromes. Let's step through it with a sample text based on a valid one that they gave: aaabbbbb (the only difference between this and their example is that there is an extra b).

Your first for loop counts how many times the letters appear in the string. In this case, 3 a and 5 b with all the other characters showing up 0 times (quick aside, the end of the range function is exclusive so this would not count any z characters that might show up).

The next for loop counts how many character there are that show up only once in the string. This string is made up of multiple a and b characters, more than the check that you have for if key == 1 so it doesn't trigger it. Since the count is less than 1, it returns YES and exits. However aaabbbbb is not a palindrome unscrambled.

Suggestion

To fix it, I would suggest having more than just one function so you can break down exactly what you need. For example, you can have a function that would return a list of all the unscrambled possibilities.

def allUnscrambled(string)->list:
    # find all possible iterations of the string
    # if given 'aabb', return 'aabb', 'abab', 'abba', 'bbaa', 'baba', 'baab'
    return lstOfStrings

After this, create a palindrome checker. You can use the one shown by Dmitriy or create your own.

def checkIfPalindrome(string)->bool:
    # determine if the given string is a palindrome
    return isOrNotPalindrome

Put the two together to get a function that will, given a list of strings, determine if at least one of them is a palindrome. If it is, that means the original string is an anagrammed palindrome.

def palindromeInList(lst)->bool:
    # given the list of strings from allUnscrambled(str), is any of them a palindrome?
    return isPalindromeInList

Your function gameOfThrones(s) can then call this palindromeInList( allUnscrambled(s) ) and then return YES or NO depending on the result. Breaking it up into smaller pieces and delegating tasks is usually a good way to handle these problems.

CodePudding user response：

Corrected the logic in my solution. I was just comparing key == 1 and not with every odd element.

So the corrected code looks like:

for key in alpha_dict.values():
    if key % 2 == 1:
        counter  = 1

It passes all the testcases on HackerRank website.