[Challenge] Palindrome Detector

challenge

#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.'))

#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:


#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.


#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.


#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


#22

As @chrinkus pointed out, the (apparently recently updated) rules state that it is now preferred NOT to have your repl.it code previewed here as embedded interpreter. Instead, code in the challenge topics should be formatted with common code tags as described here. So all you need to do to create the ‘optimal submission’ is to add your code as such in your post so it can be read without having to go to your repl.it page.
If in another topic you still need to embed repl.it code, just copy its url (not the embed link) without other text on its own line.


#23

This is my try at the intermediate (and maybe hard :smile: ) in Java.
Here’s the link to the code https://repl.it/JIAN/2

public class Main 
{
  public static void main (String[] args)
  {
    String input = "helllleh1";
    System.out.println(isPermPalindrome(input)); 
  }
  public static boolean isPermPalindrome(String input)
  {
    int[] alphanum = new int[36]; // to know if a letter appeared an even or odd number of times
    for(int i = 0; i < alphanum.length; i++)
      alphanum[i] = 0;
    input = input.toLowerCase(); // take care of case sensitivity
    for(int i = 0; i < input.length(); i++)
    {
      char c = input.charAt(i);
      if(Character.isLetter(c)) //only consider letters
      {
        alphanum[c-'a'] = 1 - alphanum[c-'a'];
      }
      else if(Character.isDigit(c)) //consider digits too
      {
        alphanum[26+(c-'0')] = 1 - alphanum[26+(c-'0')];
      }
    }
    int unique = 0;
    for(int i = 0; i < alphanum.length; i++)
      unique += alphanum[i];
    return (unique == 1 || unique == 0); // at most one character should occur an odd number of times
  }
}

#25

Code on repl.it

Used Javascript for the intermediate difficulty.

I first removed capitalisation from the input and then extracted [a-z0-9], removing spaces and punctuation. The assignment was to inlcude numbers, but it did not say that we should ignore them.

The idea was to count all the characters in the input string and return false when there are more than 1 odd characters.

And return true for all the other cases.

function isPermPalindrome(input) {
	// Format the input
	input = input.toLowerCase();
	input = input.match(/[a-z0-9]/g);


	// Make a variable to store the character count
	var collection = {};

	// Count the characters
	for(var i = 0; i < input.length; i++) {
		var currentChar = input[i];

		if(collection[currentChar]) {
			collection[currentChar] = collection[currentChar] + 1;
		} else {
			collection[currentChar] = 1;
		}
	}

	// Count the amount odd characters
	/*
	 |   ODD   |   EVEN   |
	 |---------|----------|
	 |   0     |   Any    | => True
	 |---------|----------|
	 |   1     |   Any    | => True
	 |---------|----------|
	 |   +1    |   Any    | => False
	 */
	var odd = 0;

	for(var character in collection) {
		if(collection[character] % 2 != 0) {
			odd++;
		}

		if(odd > 1) {
			return false;
		}
	}

	return true;
}

#26

Main idea:

  1. Even number of symbols instances can form polindrome string (‘ABBA’)
  2. Only one symbol allowed to have odd number of instances (‘ada’)

Here we go with Python3: https://repl.it/JIlS/0

def isPermPalindrome(s):
    # built hash table:
    # hash value True - odd instances of a symbol
    s_hash = {}
    for symb in s.lower():
        if symb.isalpha() or symb.isdigit():
            if symb in s_hash:
                del s_hash[symb]
            else:
                s_hash[symb] = True

    # Check no more than 1 value in the hash
    return len(s_hash) <= 1
    
print( isPermPalindrome("Science Bros.") )

#27

Here’s my entry for hard challenge in Python. The code counts occurences of all allowed chars, then recognizes a palindrome permutation if:

  • every char has even amount of occurrences (eg. “abba”)
    or
  • every char except one has even amount of occurrences, if string length (counting allowed chars only) is odd (eg. “kayak”)
def isPermPalindrome(text):
    charcount = [0] * 36                 # [0123456789abcdefghijklmnopqrstuvwxyz]
    for char in (text):
        char = ord(char) | 32              # to lowercase
        if   char >= 48 and char <=  57:   # count numbers
            charcount[char-48] += 1
        elif char >= 97 and char <= 122:   # count letters, ignore other
            charcount[char-87] += 1

    charsum = sum(charcount)            
    if charsum == 0: return False    # no valid chars in the string
    tlodd = charsum % 2              # odd text length flag
    for i in charcount:
        if   i%2 == 0: continue
        elif i%2 and tlodd:          # odd-sized string can have 1 unpaired char
            tlodd = 0                      
        else:                        # another odd count
            return False
    return True

Single iteration, used separate sum(charcount) rather than count inside the loop as it turns out to be faster. Settled on no O(n) string operations at the cost of some speed to keep memory use low.
repl.it