🎓 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
In this blog post, we're going to explore a classic problem in string manipulation - finding the longest palindromic substring within a given string. This problem is a common question in coding interviews and is excellent for understanding string processing in Java.
Problem
Given a string s, the task is to find the longest palindromic substring in s.
Examples:
Input: "babad"
Output: "bab" (Note: "aba" is also a valid answer)
Input: "cbbd"
Output: "bb"
2. Solution Steps
1. If the input string is null or its length is less than 1, return an empty string.
2. Create two variables to store the start and end of the longest palindrome found.
3. Iterate through the string, treating each character as the center of a potential palindrome.
4. Check for palindromes that have odd and even lengths and update the start and end variables if a longer palindrome is found.
5. After the iteration, return the substring from the start to the end + 1.
3. Code Program
public class Solution {
// Main method to test the longest palindrome finder
public static void main(String[] args) {
String input1 = "babad";
String input2 = "cbbd";
System.out.println("Longest Palindromic Substring of '" + input1 + "': " + longestPalindrome(input1));
System.out.println("Longest Palindromic Substring of '" + input2 + "': " + longestPalindrome(input2));
}
// Method to find the longest palindromic substring
public static String longestPalindrome(String s) {
if (s == null || s.length() < 1) return ""; // Check for null or empty string
int start = 0, end = 0; // Variables to mark the start and end of the longest palindrome
for (int i = 0; i < s.length(); i++) {
int len1 = expandFromCenter(s, i, i); // Length of palindrome for odd length
int len2 = expandFromCenter(s, i, i + 1); // Length of palindrome for even length
int len = Math.max(len1, len2); // Maximum length from the two cases
if (len > end - start) { // Update start and end if a longer palindrome is found
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1); // Return the longest palindromic substring
}
// Helper method to expand around the center and find palindrome length
private static int expandFromCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1; // Length of the palindrome
}
}
Output:
Longest Palindromic Substring of 'babad': bab Longest Palindromic Substring of 'cbbd': bb
Explanation:
For the input "babad", the longest palindromic substrings are "bab" and "aba", each with a length of 3.
The method longestPalindrome checks for palindromes by expanding around potential centers of the palindrome (including handling both odd and even length palindromes).
Similarly, for the input "cbbd", the longest palindromic substring is "bb".
The algorithm efficiently finds the longest palindromic substring with a complexity of O(n^2), where n is the length of the string.
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