[Challenge] Palindrome Detector

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.

1 Like

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
  }
}

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;
}

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.") )
1 Like

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

Here is my interesting take on the Basic Challenge in Python 2.7 https://repl.it/JEHj/29

After realizing that most entries determine whether or not a word could even be considered before testing, my code just goes ahead and brute forces generation and testing of permutations. Due to not enough memory, my code only works for up to 10 character strings (not counting whitespace).

# First, I defined how to check if a word is a palindrome by reversing the string and comparing it to the original.
def isPalindrome(text):
    def reverse(text):
        anti_text = ""
        for char in text[::-1]:
            anti_text += char
        return anti_text
    if reverse(text) == text:
        return True
    else:
        return False

# Next, I defined how to generate a list of all possible permutations of a string. I did this using recursion. As a result, the program is very sluggish if the length of the string is longer than seven characters (not counting whitespace) and will actually run out of memory for strings longer than 10 characters (not counting whitespace).
def getPerms(text):
    if len(text) == 1:
        return text
    recursive_perms = []
    for c in text:
        for perm in getPerms(text.replace(c, "", 1)):
            recursive_perms.append(c + perm)
    return recursive_perms

# Next, I went through and checked if each permutation was a palindrome. If one or more permutations are palindromes, it returns true. If no permutations are palindromes, it returns false.
def isPermPalindrome(text):
    text = text.replace(" ", "")
    word = text.lower()
    perms = getPerms(word)
    result = bool
    for perm in perms:
        if isPalindrome(perm) == True:
            result = True
    if result == True:
        return True
    else:
        return False

test = raw_input("Input:")    
print "Output:", isPermPalindrome(test)
1 Like

Consider this:

def isPalindrome(text):
    return text == text[::-1]

As for memory problems, try converting your recursive function into a generator (read up on yield) so you can iterate on it directly. Also if the objective is to test whether at least 1 palindrome exists, break immediately after finding the first one.

1 Like

Python 3 All difficulties

# Program to test if a given string is a permutation of a palindrome.

# inp = input
def isPermPalindrome(inp):
    
    # Make input into list of lowercase input
    inp = list(inp.lower())

    # Remove everything that is not alphanumeric
    for char in inp:
        if char.isalnum() == False:
            inp.remove(char)

    # Create variable and loop though to see if there is only 0 or 1 odd char
    num_of_odd_char = 0

    for char in inp:
        if inp.count(char) % 2 == 1:
            num_of_odd_char += 1
            inp.remove(char)

    # If there is more than 1 odd character counted it is not a palindrome
    if num_of_odd_char > 1:
        return False
    else:
        del num_of_odd_char

    return True

isPermPalindrome("Science Bros.")
print(isPermPalindrome("Science Bros."))

Excuse me, while I go hit my head against the wall a couple thousand times…

Anyway, here is my new code, based upon your recommendations… https://repl.it/JEHj/36

# First, I defined how to check if a word is a palindrome by reversing the string and comparing it to the original.
def isPalindrome(text):
    return text == text[::-1]

# Next, I defined how to generate a list of all possible permutations of a string. I did this using recursion. 
# As a result, the program is very sluggish if the length of the string is longer than seven characters (not counting whitespace),
# and will actually run out of memory for strings longer than 10 characters (not counting whitespace). 
def getPerms(text):
    if len(text) == 1:
        return text
    recursive_perms = []
    for c in text:
        for perm in getPerms(text.replace(c, "", 1)):
            recursive_perms.append(c + perm)
    return recursive_perms

# Next, I checked if any permutation was a palindrome. If any permutation is a palindrome, it returns True and breaks. 
# If no permutations are palindromes, it returns False.
def isPermPalindrome(text):
    text = text.replace(" ", "")
    word = text.lower()
    perms = getPerms(word)
    result = False
    for perm in perms:
        if isPalindrome(perm) == True:
            result = True
            break
    return result

# This is just the code to run test instances.
test_1 = raw_input("Input:")    
print "Output:", isPermPalindrome(test_1)
test_2 = raw_input("Input:")
print "Output:", isPermPalindrome(test_2)
test_3 = raw_input("Input:")
print "Output:", isPermPalindrome(test_3)

# Side note, this program works well for some of the most common single-word palindromes and their corresponding permutations.
# Unfortunately, the word tattarrattat (The longest palindromic word in the Oxford English Dictionary) does not return anything.
1 Like

Basic difficulty. Python.

To determine weather a string could be a palindrome it has to have either even number of each letter or even number of each letter + 1. To test that I reduce the string to set of unique letters and then I search for letters that occur uneven number of times. Any string with more than one letter without pair is not able to produce palindrome = False.

 def isPermPalindrome(s=None):                                                    
     singles = 0                                                                  
     s = s.lower()                                                                
     for l in set(s):                                                             
         if s.count(l) % 2 != 0:                                                  
             singles += 1                                                         
     if singles > 1:                                                              
         return False                                                             
     else:                                                                        
         return True

Sorry for the super late response!

This is a neat little challenge.
As almost everyone realised creating every permutation possible and checking if that is a palindrome would be crazy inefficient.

The best solution is to make sure each letter has a pair, at the end at most one letter can be left,

In my opinion, the two most elegant solutions using this criteria were the first two. So the winners are @betamaster97156 and @tagrockstar79958. Congrats guys!

Don’t forget there is a new challenge published every Wednesday so keep coming back for more!

5 Likes