Tuesday, September 27, 2022
HomePythonDiscover Longest Palindrome in a Python String (Straightforward) – Finxter

Discover Longest Palindrome in a Python String (Straightforward) – Finxter


Coding Problem

💬 Problem: Given a string. Learn how to discover the longest palindrome within the string?

Determine: The string 'locoannamadam' comprises a number of palindromes. The longest palindrome is 'madam'.

For comprehensibility, enable me to rapidly add a definition of the time period palindrome:

💡 Definition: A palindrome is a sequence of characters that reads the identical backward as ahead equivalent to 'madam', 'anna', or '101'.

This text needs to provide you a fast and straightforward answer in Python. First, we’ll resolve the better however vital drawback of checking if a substring is a palindrome within the first place:

Verify If Substring is Palindrome

You may simply test if a substring is a palindrome through the use of the slicing expression phrase == phrase[::-1] that evaluates to True if the phrase is similar ahead and backward, i.e., it’s a palindrome.

👉 Really useful Tutorial: Python Palindromes One-Liner

Subsequent, we’ll discover discover the longest substring in a Python string that can be a Palindrome. Yow will discover our palindrome checker within the code answer (highlighted):

Discover Longest Substring That’s Palindrome

The brute-force method to discovering the longest palindrome in a string is to iterate over all substrings in a nested for loop. Then test every substring if it’s a palindrome utilizing phrase == phrase[::-1]. Preserve monitor of the longest palindrome utilizing the len() operate in an if situation.

Right here’s the total answer:

def find_longest_palindrome(s):
    longest=""
    n = len(s)
    for i in vary(n):
        for j in vary(i+1,n+1):
            phrase = s[i:j]
            if phrase == phrase[::-1]:
                if len(phrase)>len(longest):
                    longest = phrase          
    return longest


print(find_longest_palindrome('locoannamadam'))
# madam

print(find_longest_palindrome('anna'))
# anna

print(find_longest_palindrome('abc'))
# a

Runtime Complexity

This has cubic runtime complexity, i.e., for a string with size n, we have to test O(n*n) completely different phrases. Every phrase could have as much as n characters, thus the palindrome test itself is O(n). Collectively, this yields runtime complexity of O(n*n*n) = O(n³).

Dialogue and Higher Options

Is that this the perfect we will do?

No! The perfect we will theoretically do is a linear runtime complexity and linear area complexity referred to as Manacher’s Algorithm. The thought is to decide on a number of “palindrome facilities” and develop these facilities one step at a time by including characters to the left or the appropriate.

Nevertheless, you’re not anticipated to give you this your self in a coding interview.

Quadratic Programming Concept

What some interviewers could count on is to give you a “dynamic programming” concept the place you assemble a Boolean matrix.

Knowledge Construction: Every cell (i,j) of the Boolean Matrix is True if the string s[i:j] is a Palindrome and False in any other case. The cell that’s True and has the best worth for j-i represents the longest Palindrome.

Algorithm: Fill the info construction with Boolean values. You may assemble a cell (i,j) from the smaller cells simply by checking if the smaller substring s[i+1:j-1] is a Palindrome and the primary and final characters s[i] and s[j] are the identical. Set the cell to False or True accordingly. Initialize the info construction with diagonal values (i,i) == True.

Word we do NOT use Python indexing on this description, i.e., the tip index of a slice is included.

Right here’s a fast overview of this concept:

🧩 Train: Implement this concept in Python code and send it to me!


RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments