🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
A palindrome is a word, number, phrase, or sequence of characters that reads the same forward and backward. Examples include "madam" or "aba". In this post, we will implement and understand an algorithm to find the longest palindrome substring within a given string.
2. Program Overview
1. Define a function to expand around the center and check for a palindrome.
2. Iterate through each character of the string and consider it as a center to expand and find palindromes.
3. Store and update the longest palindrome substring.
4. Return the longest palindrome substring.
3. Code Program
def longest_palindrome(s: str) -> str:
"""Find the longest palindrome substring in s."""
if not s:
return ""
start = 0
end = 0
for i in range(len(s)):
len1 = expand_around_center(s, i, i)
len2 = expand_around_center(s, i, i + 1)
max_len = max(len1, len2)
if max_len > (end - start):
start = i - (max_len - 1) // 2
end = i + max_len // 2
return s[start:end+1]
def expand_around_center(s: str, left: int, right: int) -> int:
"""Helper function to expand around the center and return length."""
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
# Test
input_str = "babad"
print(f"The longest palindrome substring of {input_str} is: {longest_palindrome(input_str)}")
Output:
The longest palindrome substring of babad is: bab (Note: The string "babad" also has another palindrome "aba", but the function returns the first longest palindrome it finds.)
4. Step By Step Explanation
1. We start with a helper function expand_around_center that takes a string and two indices as arguments. It tries to expand outwards from the center and returns the length of the palindrome.
2. In the main function longest_palindrome, for each character in the string, we treat it as the center of a possible palindrome. We also account for even length palindromes by considering two adjacent characters as the center.
3. We use the helper function to expand from the center and check for palindromes, storing the start and end indices of the longest palindrome found.
4. Finally, we extract and return the longest palindrome substring using slicing.
Using this approach, we efficiently check for palindrome substrings in the string and return the longest one found.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment