CODEWITHSUNDEEP
pythonstringpalindrome
ryand
ryand

Reputation: 131

Find the length of the palindrome that can be made from a string in Python

I try to make program to find the length of the palindrome that can be made from a string in Python, but I got wrong result.

This is my program but I still get wrong results, maybe anyone can help me to fixed this.

from typing import Counter
def checkpalindrom(s):
    mid = len(s)/2
    end = len(s)-1
    i = 0
    while  i<= mid:
        if s[i]!= s[end-i]:
            return False
    return True
def deletepalindrom(s):
    if deletepalindrom(s)==True:
        return 0
    min = 100
    x = 0
    while x < len(s):
        temp = s
        temp.remove(1)
        Counter = deletepalindrom(temp)+1
        if Counter<=min:
            min = Counter
n = int(input())
for y in range(n):
    s = input()
    print(len(s)- deletpalindrom(s))

I got a redline in line print(len(s)- deletpalindrom(s)) to show the length and also in line temp.remove(1) got 'str' object has no attribute 'remove'.

Upvotes: 0

Views: 599

Answers (2)

hilberts_drinking_problem
hilberts_drinking_problem

Reputation: 11602

It is helpful to make the following observations:

  • In a palindrome p, at most one letter appears an odd number of times.

  • The maximum length of a palindrome formed using letters in a string w is fully determined by the letter "frequencies" of the string w. For example, the answer for aab is the same as the answer for bba.

With the observations in mind, here is one solution using collections.Counter.

from collections import Counter

xs = ['wewewe', 'pelatnas', 'kedua', 'di', 'jogja']
ys = [5, 3, 1, 1, 3]

def pal_len(s):
  result = 0
  # letter frequencies
  ctr = Counter(s)
  # False only if each letter appears an even number of times
  have_spare = False
  for k, v in ctr.items():
    # letter k appears v times
    # if v is even, we can add v characters to the palindrome
    # if v is odd, we can add v - v%2 characters to the palindrome
    remainder = v % 2
    result += v - remainder
    if remainder:
      have_spare = True
  # at this point, have_spare == True whenever
  # there is a character that appears an odd number of times in s
  # we can insert such a character in the middle of the palindrome
  return result + have_spare
  
assert all(pal_len(x) == y for x, y in zip(xs, ys))

Upvotes: 0

Georgy Kopshteyn
Georgy Kopshteyn

Reputation: 763

You can do the following to achieve what you want:

from itertools import permutations


def get_len_palindrome(string):
    all_permutations = [''.join(p) for p in permutations(string)]
    lst_palindrome_lengths = []

    for permutation in all_permutations:
        for i in range(len(permutation)+1):
            if permutation[:i] == permutation[:i][::-1]:
                lst_palindrome_lengths.append(i)

    lst_palindrome_lengths.sort(reverse=True)
    return lst_palindrome_lengths[0]
            
n = int(input())
for y in range(n):
    s = input()
    print(get_len_palindrome(s))

The function get_len_palindrome(string) first utilises the permutations method of the itertools module to obtain all permutations of a given string, then, drawing from a pythonic way to check for palindromes suggested here, uses the permutations obtained this way to determine the lengths of palindromes constructed from this string and returns the maximum length.

Upvotes: 1

Related Questions