[Challenge] Palindrome Detector

Events & Challenges
1

#Code Challenge #12: June 28, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge was reported to have been asked in interviews at Facebook:

###Basic Difficulty

Write a function, isPermPalindrome, that will test if a given string is a permutation of a palindrome.

  • Function Name: isPermPalindrome

  • Input: a String consisting only of lowercase letter characters

  • Output: a boolean, true if the string is a permutation of a palindrome and false if the string is not a permutation of a palindrome

  • Examples:

  • isPermPalindrome("kayak") => true

  • isPermPalindrome("yakak") => true

  • Permutations are all possible arrangements of a collection of things, where the order is important.

  • From Merriam Webster, a palindrome is a “word, verse, or sentence (such as “Able was I ere I saw Elba”) or a number (such as 1881) that reads the same backward or forward.” Read more about palindromes here or see some interesting examples here.

#####Find out more about basic challenges.

###Intermediate difficulty

As above, but isPermPalindrome should now be able to account for punctuation, spaces, and capitalization in the input string.

  • Your input string may now include spaces, numbers, punctuation, and capitalization, but in assessing whether the string is a palindrome or not, spaces, punctuation, and capitalization does not matter. For example, akyKa is a permutation of Kayak, but we don’t care that there is one upper case K and one lower case k in Kayak – this is still a palindrome.
  • Example: isPermPalindrome("Science Bros.") => false

#####Find out more about intermediate challenges.

###Hard Difficulty

Write isPermPalindrome as efficiently as possible.

#####Find out more about hard challenges and Big O

Reply to this thread with a link to your code on repl.it and paste your properly formatted code to participate! Don’t just submit your code, remember to explain your solution, too! If you want to be considered as the winner, your function must have the correct name and provide output in the format specified above, you also need to abide by our other simple rules.

As always solutions using imports to do all the heavy lifting such as itertools will not be considered for the winner.

The fine print:

Click the links to find out more about:

2 Likes
2

Python 3.6 https://repl.it/JFbS/0


def isPermPalindrome(string: str) -> bool:

    # here I remove non alphanumerical characters from the string, and lower case the string.
    string = ''.join(char.lower() for char in string if char.isalnum())

    # Here the half length of the string is prepared. It's needed in he actual comparison below. By casting the result
    # to int, we are sure to get a round down, in case if decimals.
    half_length: int = int(len(string) / 2)

    # As the final step, we need to compare the first half of the string to the reversed second half. But first we need
    # to figure out of we need to adjust how we compare. Basically if the length of the string is even or uneven.
    
    # If it's even: Straight comparison of the two halves.
    # If it's uneven: We have to pivot around the middle character. You can chose to include it in both halves or
    # exclude it from both halves in the comparison. Makes no difference. I chose to exclude.

    # o o o o   o o o o  no pivot when even length string
    # o o o o x o o o o  pivot when uneven length string
    
    # We figure out if we should adjust for pivot or not
    if len(string) % 2 == 0:
        middle_offset = 0
    else:
        middle_offset = 1

    # The first half of the string is compared to the reversed 2nd half. If they are equal it's a palindrome!
    if string[:half_length] == ''.join(char for char in (reversed(string[half_length+middle_offset:]))):
        return True

    return False


if __name__ == '__main__':

    print(isPermPalindrome('Hello World'))
    print(isPermPalindrome('Able was I ere I saw Elba'))
    print(isPermPalindrome('1881'))
    print(isPermPalindrome('Eva, can I see bees in a cave?'))
    print(isPermPalindrome('What is going on here? ! !'))
3

https://repl.it/JFb7

Use python dict to track the unique item, remove the character from dict if duplicate was found or add it to dict if duplicate not found. Palindrome means that the resulting dict should have 0 or 1 uniq key.

Perhaps could do it from both end (2 character at a time) per loop, but that doesn’t speed up anything as we still have the same IO access, we run half the for loop but may spend some cpu cycle in additional if statement checking.
A better performance optimization will be to do loop unrolling to do multiple character per loop that match with cpu cache line size.

import string
d={}
def isPermPalindrome(str):
  for c in list(str.lower().translate(None, string.punctuation).translate(None, " ")):
    if d.has_key(c):
      del d[c]
    else:
      d[c]=1
  return len(d)<=1

print isPermPalindrome("kayak")
print isPermPalindrome("yakak")
print isPermPalindrome("Science Bros.")
4 Likes
4

I just realized I could try the deque from the collections module for this. I’m not sure it makes the code run faster, but it does make the code much more readable and that also counts for something :slight_smile:

from collections import deque


def isPermPalindrome(string_deque: str) -> bool:

    string_deque = deque(''.join(char.lower() for char in string_deque if char.isalnum()))

    while True:
        if string_deque.pop() != string_deque.popleft():
            return False

        if len(string_deque) <= 1:
            break

    return True

if __name__ == '__main__':

    print(isPermPalindrome('Hello World'))
    print(isPermPalindrome('Able was I ere I saw Elba'))
    print(isPermPalindrome('1881'))
    print(isPermPalindrome('Eva, can I see bees in a cave?'))
    print(isPermPalindrome('What is going on here? ! !'))
5

Newbie, don’t know how to use repLit, sorry.

Not the most elegant, but I clean it up to just the chars with reg ex then try and match it to the cleaned-up version, reversed.

function isPermPalindrome(str) {
var cleanStr = str.toLowerCase().replace(/[\W_]/g, ‘’);
var reverseStr = cleanStr.split(’’).reverse().join(’’);
return reverseStr === cleanStr;
}

6

Alright. This should do it. https://repl.it/JFsZ/4

'use strict';

function isPermPalindrome(words){
    // drop case, drop punctuation
    // we can't just use \w regex because of _
    const string = words.toLowerCase().replace(/[^a-z0-9]/g,'');

    // break the words into an array
    let chars = string.split('');

    const pivot = [];
    // we work regardless if the input is odd or even length.
    while(chars.length > 1){
        let char = chars.pop();                // Grad a buddy
        let match = chars.indexOf(char);       // Does he have a pal?
        switch(true){
          case match === -1: pivot.push(char); // I'm not your friend guy!
          case pivot.length > 1: return false; // Blame Canada!
          case match > -1: chars.splice(match, 1);
        }
    }
    // looks like a palindrome or a permutation of one to me
    return true;
}


console.log(isPermPalindrome('ABBA'))                           // true
console.log(isPermPalindrome('AABB'))                           // true
console.log(isPermPalindrome('1881'))                           // true
console.log(isPermPalindrome('8811'))                           // true
console.log(isPermPalindrome('Hello World'))                    // false
console.log(isPermPalindrome('Able was I ere I saw Elba'))      // true
console.log(isPermPalindrome('Eva, can I see bees in a cave?')) // true
console.log(isPermPalindrome('What is going on here? ! !'))     // false
console.log(isPermPalindrome('Science Bros.'))                  // false
7

I went a different way on this. The core definition of a palindrome permutation is in the character frequencies:

  • In a palindrome with an even number of characters, all unique letters must repeat an even number of times
  • If the palindrome has an odd number of characters, there is exactly one letter that will have an odd number of occurrences (the pivot letter)

So, I just take all the letters in our string and use the collections module to list the number of occurrences. This way we don’t have to generate any permutations in the code.

I’m sure this is a little sloppy, I don’t code often enough to know the most efficient stuff.

Also, I fully admit to stealing tagrockstar’s code above for normalizing the capitalization and getting rid of non-alpha characters.

Code on repl.it: https://repl.it/JGDX/0\

import collections

def isPermPalindrome(pal):
    oddCount = 0 # this will track the number of times a letter appears an odd number of times
    strList = ''.join(char.lower() for char in pal if char.isalnum()) # normalize caps and clear punctuation and spaces
    alphaCount = collections.Counter(strList) # Alphacount will be a dictionary of each unique letter along with how frequently it appears
    for c in alphaCount.values():
        if (c % 2 == 1):
            oddCount = oddCount + 1 # looks for letters that appear an odd number of tiems

    if (len(pal) % 2 == 0): # if the string length is even, there should be NO letters appearing an odd number of times
        if (oddCount == 0):
            return True
        else:
            return False
    else:                   # if the string length is odd, there should be exactly ONE letter appearing an odd number of times (the pivot letter)
        if (oddCount == 1):
            return True
        else:
            return False

print(isPermPalindrome('Hello'))
print(isPermPalindrome('Kayak'))
print(isPermPalindrome('yakak'))
print(isPermPalindrome('Science Bros.'))
6 Likes
8

Here’s my attempt at this challenge, in intermediate difficulty: https://repl.it/JGGV/6

This time I needed some help with the logic, so I searched a bit on google and this comment was quite helpful: https://stackoverflow.com/a/31224782/7601147
I’m sorry I couldn’t completely come up with the answer on my own, but I’m trying to be straightforward and transparent about it. If you still want me to delete my reply or something please do tell me, and I’d completely understand it.

#this comment helped me with the logic for the script: https://stackoverflow.com/a/31224782/7601147

#receive a string and count how many times each unique letter appears
#if all letters have an even number of appearances then String is a permutation of a palindrome
#else if there's only one letter that appears an odd number of times, String is still a permutation of a palindrome
#if there's more than one letter with an odd number of appearances then String is not a permutation of a palindrome

#Intermediate difficulty
#imports
from collections import Counter

def isPermPalindrome(String):
    strippred_String = '' #will hold String filtered of spaces, punctuation and capitalized letters
    for char in String.lower(): #this gets rid of capitalized letters right off the bat
        if char == ' ': #ignore spaces
            pass
        elif char.isalnum() == False: #if char is not a letter or a digit ignore it
            pass
        else: #if char is a letter or a digit then add it to strippred_String
            strippred_String += char
            
    letter_counter = list(Counter(strippred_String).values()) #creates a list containg how many times each unique letter appears in String
    
    odd_count = 0 #this will count how many unique letters in string appear a odd number of times
    
    for num in letter_counter: #now use this loop to check how many unique letters have an odd number of appearances
        if num%2 == 0:
            pass
        else:
            odd_count += 1
            
    #if there's more than one unique letter that appears an odd number of times in String return False; else return True
    return bool(odd_count <= 1)


print('isPermPalindrome_int("kayak") =>', isPermPalindrome('kayak'))
print('isPermPalindrome_int("yakak") =>', isPermPalindrome('yakak'))
print('isPermPalindrome_int("Science Bros.") =>', isPermPalindrome('Science Bros.'))
9

Javascript Hard
https://repl.it/JGFN/5

function isPermPalindrome(str) {
  "use strict";
  const charCounts = Object.create(null);     // no inherited props
  
  for (const ch of str.toLowerCase()) {   // for each lower case char
    if(/[^a-z0-9]/.test(ch)) {            // if not an alpha char
      continue;                           // continue
    }
    
    if (charCounts[ch]) {     // if char already exists in tokens...
      charCounts[ch] += 1;    // increment it
    } else {
      charCounts[ch] = 1;     // init it to 1 (1 instance of char so far)
    }
  }
  
  let oddCounts = 0;                  // track how many odds
  for (const prop in charCounts) {
    if (charCounts[prop] % 2 === 1) {
      oddCounts += 1;
    }
  }
  
  return oddCounts > 1 ? false : true;  // only allow upto one 'odd'
}

console.log(isPermPalindrome("radar"));
console.log(isPermPalindrome("A man, a plan, a canal, Panama"));
console.log(isPermPalindrome("today I punched a frog"));
console.log(isPermPalindrome("da R ! da"));

Note: Changed regex to include numbers as I see the instructions do not exclude them.

EDIT: I approached this with the goal of finding out how many characters are repeated an odd number of times in the string. Since a palindrome could only have a single character repeated an odd number of times (the fulcrum ‘d’ of ‘radar’) I wanted to keep track of letter repetitions.

Knowing that we’d want to not count whitespace or punctuation, and NOT wanting to actually have to mess with those characters as properties, I used a regex to skip over those characters.

EDIT 2: Changed some variable names to be more semantically appropriate.

EDIT 3: Forgot to narrow my regex after using String.toLowercase()

10

Solution is here (Python 3): https://repl.it/JG2H/0

Basic idea is to iterate over (lowercase characters in) a string using a for loop. Instances of each letter are counted using a dictionary. All punctuation and whitespace is iterated over and ignored.

Once the characters are counted a second for loop is used to iterate over the dictionary values, each odd number is counted. Since palindromes must “mirror themselves” in letter order, only one letter can be repeated in the string. The function returns False if there are two or more characters occurring an odd number of times in the string.

It’s not the most elegant solution, but I did it in about 20 minutes and I believe it is still a n = 2O algorithm.

12

Check out the extra information (mainly the How To Participate part) for this and other stuff you may want to know

13

Hard difficulty (JavaScript): https://repl.it/JGyJ/2

Like some of the previous solutions, I also found the RegExp possibility, but decided not to use it since it may get close to the ‘imports that do the heavy lifting’ that would take away a large chunk of the challenge.

The premise of this code is to check each character in the testString against a whitelist, permittableChars. Any characters that get passed will be checked against foundChars, a list of characters found earlier in the loop. If no match is found, the character is added to the array. If a matching character is found, its match is removed from foundChars. At the end of the loop through all testString’s characters, foundChars contains all characters that occur in testString in an odd amount.
If foundChars.length === 0, testString is an even-number length palindrome
If foundChars.length === 1, testString is an odd-number length palindrome
If foundChars.length > 1, testString is not a palindrome

 isPermPalindrome(".0123456789876543210");      //true
 isPermPalindrome(".01234567898765432100");     //false
 isPermPalindrome("Science Bros.");             //false
 isPermPalindrome("Able was I ere I saw Elba"); //true
 
 function isPermPalindrome(testString) {
     //list of all permittable characters to exclude spaces, punctuations, any other symbols, and Order 66
     var permittableChars = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
     //array of all characters that have been detected, but not yet matched
     var foundChars = [];
     //currently tested character in the loop
     var testChar = '';
     for (i = 0; i < testString.length; i++) {
         testChar = testString.substr(i,1).toLowerCase();
         //check if character is whitelisted and paired
         if (permittableChars.indexOf(testChar) !== -1 && foundChars.indexOf(testChar) !== -1) {
             foundChars.splice(foundChars.indexOf(testChar), 1);
         //check if character is whitelisted and unpaired
         } else if (permittableChars.indexOf(testChar) !== -1 && foundChars.indexOf(testChar) === -1) {
             foundChars.push(testChar);
         }
     }
     if (foundChars.length > 1) {
         console.log(false);
     } else {
         console.log(true);
     }
 }

PS: was it recently added to the extra information page that it is preferred NOT to use the repl.it preview box, but instead just provide the link?

14

Intermediate/Hard Difficulty in Python: https://repl.it/JHLS/15

A palindrome needs to have even number of all letters/digits (with possibly one letter as an exception). The function creates a set to store odd-numbered letters/digits and traverses through input string. When a letter/digit appears in string for a second time, it is removed from the set. It is expected that if an input string is a palindrome, the loop will end with an empty set (all letters in even numbers) or a set containing a single letter (a pivot letter in palindrome).

To account for capitalization, the function first transforms the input string into lowercase. To deal with whitespaces and punctuation, each element is checked with concatenated string.whitespace and string.punctiation.

import string

def isPermPalindrome(s):
  rubbish = string.punctuation + string.whitespace
  letters = set()
  s = string.lower(s)
  for a in s:
    if a in rubbish:
      continue
    if a in letters:
      letters.remove(a)
    else:
      letters.add(a)
  if len(letters) > 1:
    return False
  else:
    return True
    

a = 'yakak'
b = 'Science Bros.'
c = 'kayak'
print isPermPalindrome(c)
15

From what i can see, you only check if the input is a palindrome, not if it is a permutation of a palindrome. Running string like “1188” or “yakak” through the function should return True, because the characters can be rearranged to form a palindrome.

16

Oy . .you are right! Didnt catch the full scope of the challenge. Oh dear oh dear :grimacing:

4 Likes
17

Hey Omnishift,

Yep, we asked people to change up the way that they submit – with more of an emphasis on formatted pasted code than the Repl.it preview box – partially because when so many people include their repl.it previews, it dramatically increased the time it takes to load the page. We definitely still want people to include a repl.it link so that we can assess answers, just don’t have it so that it embeds.

1 Like
18

Hey hiro_protagonist,

How did you embed your interpreter like that? I’m following the docs but I can’t seem to make it work.

19

ok … so we try again . .

Python3.6: https://repl.it/JH68/1

from collections import defaultdict


def isPermPalindrome(string: str) -> bool:

    # cleaning non alphanumerical characters from the string, and lower caseing.
    string = ''.join(char.lower() for char in string if char.isalnum())

    # counting occurrence of each type of letter
    count_dict = defaultdict(int)
    for char in string:
        count_dict[char] += 1

    # counting occurrence of chars with an odd occurrence
    odd_count = 0
    for value in count_dict.values():

        if value % 2 != 0:
            odd_count += 1

    # if all chars have an even occurrence we know it can form a palindrome
    # if there is a single char with an odd occurrence, we also know we can form a palindrome of the letters
    # if there are more than one odd occurrence letters, it is not possible to form a palindrome

    return odd_count <= 1


print(isPermPalindrome('Hello World'))
print(isPermPalindrome('Able was I ere I saw Elba'))
print(isPermPalindrome('1881'))
print(isPermPalindrome('1818'))
print(isPermPalindrome('1188'))
print(isPermPalindrome('Eva, can I see bees in a cave?'))
print(isPermPalindrome('Eva, can bees I see in a cave?'))
print(isPermPalindrome('What is going on here? ! !'))
20

The post above you refers to NOT embedding the repl.it preview. Instead enter a space or any number of letters before the link to allow people to check out your code if they choose.

3 Likes
21

Here is my Python submission for all difficulties:

# accepts one string parameter, 
# consisting of letters, digits,
# spaces and punctuation
#
# returns a Boolean, representing
# whether or not, the letters, digits
# in the string are a valid permutation
# of a palindrome
def isPermPalindrome(sentence):
# the quantity of letters
# and or digits in the string
    total = 0
# dictionary count for each letter/digit
    tally = {}
# have we seen an odd count
    oddly = False
    # make one O(n) pass through
    # calculate total, of letters
    # tabulate counts, of letters
    for char in sentence:
        if char.isalnum():
            total += 1
            index = char.lower()
            tally[index] = tally.get(index, 0) +1
    # we have two different cases
    # to consider, total odds or even
    if total % 2 :
        # total is odd
        # we can have one and only one
        # odd letter count
        for entry in tally:
            if tally[entry] % 2:
            # found an odd letter count
                if oddly:
                # found another
                    return False
            # remember, what was found
                oddly = True
        return oddly
    else:
        # total is even
        # we can't have any
        # odd letter counts
        for entry in tally:
            if tally[entry] % 2:
            # found an odd letter count
                return False
    return True

def test_isPermPalindrome(test_string):
    print("isPermPalindrome(\"%s\") =>" % test_string, isPermPalindrome(test_string) )

test_isPermPalindrome("kayak")
test_isPermPalindrome("yakak")
test_isPermPalindrome("")
test_isPermPalindrome("a")
test_isPermPalindrome("ba")
test_isPermPalindrome("baa")
test_isPermPalindrome("Abba")
test_isPermPalindrome("Science Bros.")
test_isPermPalindrome("Science Bros.; Noir")
test_isPermPalindrome("Abracadabra")
test_isPermPalindrome("Call, Abracadabra!")
test_isPermPalindrome("God's dog")
test_isPermPalindrome("dog's God")
test_isPermPalindrome("no ding into dong")
test_isPermPalindrome("not ding into dong")
test_isPermPalindrome("1188")
test_isPermPalindrome("1234")

No permutations actually need to be generated.
We just need to determine whether a permutation of a palindrome is possible.

One key factor is the quanity of letters in the string.
We can ignore all other characters, such as spaces and punctuation.
If this total is odd, then only one letter can occur an odd number of times.
If this total is even, then all letters must occur an even number of times.
This is the same as, no letter can occur an odd number of times.

Here is the output of my testcases:

isPermPalindrome("kayak") => True
isPermPalindrome("yakak") => True
isPermPalindrome("") => True
isPermPalindrome("a") => True
isPermPalindrome("ba") => False
isPermPalindrome("baa") => True
isPermPalindrome("Abba") => True
isPermPalindrome("Science Bros.") => False
isPermPalindrome("Science Bros.; Noir") => True
isPermPalindrome("Abracadabra") => False
isPermPalindrome("Call, Abracadabra!") => True
isPermPalindrome("God's dog") => True
isPermPalindrome("dog's God") => True
isPermPalindrome("no ding into dong") => False
isPermPalindrome("not ding into dong") => True
isPermPalindrome("1188") => True
isPermPalindrome("1234") => False

EDIT: Wasn’t accepting digits, I fixed that now.

https://repl.it/JHXq/34