# Length of longest palindrome subsequence

Posted on

Problem

I had an interview, where I was asked to solve to this question:

Given an string str, find the maximum length of palindrome subsequence.

Example: >if str = ‘abcda’:

maximum_length = 3 ‘aca’

How can I improve this code?

``````def maximum_length_palindrome_subsequence(a):
a = list(a)
n = len(a)
table = [[0 for i in xrange(n)] for j in xrange(n)]
for i in xrange(n):
table[i][i] = 1
for gap in xrange(1,n):
for i in xrange(n-1):
h = i+gap
if h>=n:
continue
if a[i] == a[h]:
if i+1==h:
table[i][h] = 2
else:
table[i][h] = table[i+1][h-1] + 2
else:
if h<n:
table[i][h] = max(table[i+1][h], table[i][h-1])
return table[0][n-1]

print maximum_length_palindrome_subsequence('abcbda')
``````

Solution

Back to the basic of code review, what does this code do and how do you do it. At first glance I’ve got not clue what so ever this code does. I don’t know what the content of the `table` is. I don’t know what the `h` or the `gap` is referring to, and I don’t know why the `table[0][n-1]` is the correct answer.

The only thing I know is that your function is supposed to return the “maximum length palindrome subsequence” of `a`. Which is not entirely clear either. (I wrote an answer (now deleted) based on a misconception of the terms included, as I didn’t fully realize the definition of subseqence)

So let us review some unknown code:

• Vague variable naming – The variable could strongly benefit from indicating what they are actually containing. Like instead of `a`, it could be `sourceString` or `source` or `text`. The `i` and `n` is commonly known as the loop counter, and the number of elements. The `a`, `gap`, `h` and `table`, no idea what they contain. Especially the `table` is badly named.
• No comments – It would have been nice to see some comments describing what the various loops are trying to achieve, or how the table is initialized. For the method possibly some examples of valid responses.
• Break out early – As in the answer by @Dair, since `i` is ever increasing, whenever the `h >= n` you can do a `break`.
• Strange comparison, no I – You compare `a[i] == a[h]`, why? If `i == h` this will always be true. However `h = i + gap`, so this does essentially say `a[i] == a[i + gap]` which would be a little bit clearer, although I still don’t quite get why we compare this.
• Strange comparison, no II – Right below you compare `i+1 ==h`, which is the same as `i + 1 == i + gap`, which can be simplified to `gap == 1`.
• Unneeded `if h<n` – If you get this far, then it’s a given that `h < n`, as otherwise you’d `continue`‘d. Hence the `if` could be removed all together.

Based on the code so far I’m guessing that `table` holds the length of the palindrome starting at that first index and ending at last index. Not quite how it gets there, but that is my assumption. Let us rewrite the code according to this, and my comments above:

``````def maximum_length_palindrome_subsequence(text):
"""Search through text to find the maximum length of a
palindrome looking at subsequences of the text.
text = "abcda" -> palindrome: aca -> length = 3
text = "xaybzcydxe" -> palindrome: xyzyx -> length = 5
"""
text_length = len(text)

# palindrome_length is a two dimensional table of palindrome
# lengths where the first dimension is start index, and the
# second dimension is the end index of the palindrome in text

# Initialize with all zeroes
palindrome_length = [[0 for i in xrange(text_length)] for j in xrange(text_length)]

# As a base, every single character through text is a
# palindrome of length 1
for i in xrange(text_length):
palindrome_length[i][i] = 1

# Loop through the various gaps in text, and check for
# similarity for every index of the text. Update the
# palindrome_length accordingly if matching characters
for gap in xrange(1, text_length):
for i in xrange(text_length - 1):

# h is the candidate index? (or something like that?!)
h = i + gap
# If candidate index is after length of text, break out
if h >= text_length:
break

# If equal characters, update palindrome_length
if a[i] == a[h]:
if gap == 1:
palindrome_length[i][h] = 2
else:
palindrome_length[i][h] = palindrome_length[i + 1][h - 1] + 2
else:
# Characters not equal, so choose a max based upon
# ... some criteria ...
palindrome_length[i][h] = max(palindrome_length[i + 1][h],
palindrome_length[i][h - 1])

# Return the maximum length based upon entire text
return palindrome_length[0][n - 1]

print maximum_length_palindrome_subsequence('abcda')
``````

• Simplify initialization of `palindromeLength` – Instead of first filling it with `0`, and then refilling parts with `1`, you could do:

``````palindrome_length = [[ 1 if i == j else 0
for i in xrange(text_length)]
for j in xrange(text_length)]
``````
• Criteria for the `max()` – Is this somewhat related to palindromes of an even or odd length? That it chooses the longest of those two alternatives?

To conclude, your code does follow proper indentation, is a little lacking in space around operators, but the main issue is bad naming and unclear intentions of the various code blocks. There is some magic happening in this code, which could benefit from clear comments sprinkled out in the code.

Imaging what you yourself would think of your code if it was presented to you as it stood originally, but with the name `function_x` and the question: What does `function_x` do? Would you be able to answer it?

If my assumption on the `max` is correct, my final version is:

``````def maximum_length_palindrome_subsequence(text):
"""Search through text to find the maximum length of a
palindrome looking at subsequences of the text.
text = "abcda" -> palindrome: aca -> length = 3
text = "xaybzcydxe" -> palindrome: xyzyx -> length = 5
"""
text_length = len(text)

# palindromeLength is a two dimensional table of palindrome
# lengths where the first dimension is start index, and the
# second dimension is the end index of the palindrome in text

# Every character is considered a palindrom of length 1, whilst
# the rest is initialized to 0
palindrome_length = [[ 0 if i != j else 1
for i in xrange(text_length)]
for j in xrange(text_length)]

# Loop through the various gaps in text, and check for
# similarity for every index of the text. Update the
# palindrome_length accordingly if matching characters
for gap in xrange(1, text_length):
for i in xrange(text_length - 1):

# h is the candidate index? (or something like that?!)
h = i + gap
# If candidate index is after length of text, break out
if h >= text_length:
break

# If equal characters, update palindrome_length
if text[i] == text[h]:
if gap == 1:
palindrome_length[i][h] = 2
else:
palindrome_length[i][h] = palindrome_length[i + 1][h - 1] + 2
else:
# Characters not equal, so choose a max based upon
# the even or odd length palindrome length?
palindrome_length[i][h] = max(palindrome_length[i + 1][h],
palindrome_length[i][h - 1])

# Return the maximum length based upon entire text
return palindrome_length[0][text_length - 1]

print maximum_length_palindrome_subsequence('abcda')           # "3"
print maximum_length_palindrome_subsequence('xaybzcydxe')      # "5"
print maximum_length_palindrome_subsequence('abcdaabcda')      # "6"
print maximum_length_palindrome_subsequence('racecar')         # "7"
print maximum_length_palindrome_subsequence('racecars')        # "7"
print maximum_length_palindrome_subsequence('iiiiragceciars')  # "7"
``````

At the very end I presented a few more cases, to verify the correctness of the revised version.

Update: Changed to `snake_case` to conform to standards. Hopefully I didn’t break the code. 🙂

You don’t need to convert a string to a list in this case. Remove:

``````a = list(a)
``````

Also:

``````h = i+gap
if h>=n:
continue
``````

`h` is strictly increasing. Calling `continue` will stop a particular iteration quickly, but really you can stop a whole cycle, switch it out with `break`.