Find Longest Palindromic Substring

(Coding Clutch Challenge Series 101) – Coding Challenge #3

Have you ever noticed how palindromes are like mirrors, reflecting symmetry in the middle? In this challenge, we’ll find the longest palindrome within a string. This problem tests your skills in string manipulation and algorithm optimization.

Let’s dive into the details!

Coding Clutch Challenge Series 101 – All Coding Challenges

Understanding the Problem

What is a Palindrome?

A palindrome is a sequence of characters that reads the same backward as forward. For example:

• "racecar" → Palindrome
• "hello" → Not a palindrome

Problem Statement

Given a string, return the longest substring that is a palindrome. If there are multiple results, any valid one is acceptable.

Example Inputs and Outputs

• Input: "babad"
  Output: "bab" (or "aba")
• Input: "cbbd"
  Output: "bb"
• Input: "a"
  Output: "a"
• Input: ""
  Output: ""

Coding Clutch Challenge Series 101 – All Coding Challenges

Constraints

1. Input string length:
2. The string contains only lowercase English letters.

Edge Cases

1. Single-character strings.
2. Strings with all identical characters.
3. Empty string input.

Coding Clutch Challenge Series 101 – All Coding Challenges

Approach to the Solution

1. Brute-Force Method

Check every possible substring and see if it’s a palindrome.

• Steps:
  1. Generate all substrings.
  2. Check if each substring is a palindrome.
  3. Track the longest one found.
• Complexity: .

2. Center Expansion Method (Optimized)

Expand from the center of each possible palindrome.

• Steps:
  1. Consider each character and pair of characters as potential centers.
  2. Expand outward while the characters match.
  3. Track the longest palindrome found.
• Complexity: .

3. Dynamic Programming Method

Use a 2D table to track whether substrings are palindromes.

• Steps:
  1. Initialize a table where dp[i][j] is True if the substring from i to j is a palindrome.
  2. Use this information to build longer palindromes iteratively.
  3. Track the longest palindrome.
• Complexity: .

4. Manacher’s Algorithm (Advanced)

Solve the problem in linear time using a preprocessing step and a clever palindrome expansion strategy.

• Complexity: .

Coding Clutch Challenge Series 101 – All Coding Challenges

Implementation in Different Programming Languages

Python Implementation

def longest_palindrome(s):
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    longest = ""
    for i in range(len(s)):
        # Odd-length palindromes
        odd_palindrome = expand_around_center(i, i)
        # Even-length palindromes
        even_palindrome = expand_around_center(i, i + 1)

        # Update the longest palindrome
        longest = max(longest, odd_palindrome, even_palindrome, key=len)

    return longest

# Example
print(longest_palindrome("babad"))  # Output: 'bab' or 'aba'

Coding Clutch Challenge Series 101 – All Coding Challenges

C Implementation

#include <stdio.h>
#include <string.h>

void findLongestPalindrome(char* str, char* result) {
    int maxLength = 1;
    int start = 0;
    int len = strlen(str);

    for (int i = 0; i < len; i++) {
        int low = i - 1;
        int high = i + 1;

        while (low >= 0 && high < len && str[low] == str[high]) {
            if (high - low + 1 > maxLength) {
                start = low;
                maxLength = high - low + 1;
            }
            low--;
            high++;
        }
    }
    strncpy(result, str + start, maxLength);
    result[maxLength] = '\0';
}

int main() {
    char str[] = "babad";
    char result[1000];
    findLongestPalindrome(str, result);
    printf("Longest Palindromic Substring: %s\n", result);
    return 0;
}

Coding Clutch Challenge Series 101 – All Coding Challenges

C++ Implementation

#include <iostream>
#include <string>
using namespace std;

string longestPalindrome(string s) {
    int start = 0, maxLength = 1;
    int n = s.size();

    for (int i = 0; i < n; i++) {
        int low = i - 1, high = i + 1;
        while (low >= 0 && high < n && s[low] == s[high]) {
            if (high - low + 1 > maxLength) {
                start = low;
                maxLength = high - low + 1;
            }
            low--;
            high++;
        }
    }
    return s.substr(start, maxLength);
}

int main() {
    string str = "babad";
    cout << "Longest Palindromic Substring: " << longestPalindrome(str) << endl;
    return 0;
}

Coding Clutch Challenge Series 101 – All Coding Challenges

Java Implementation

public class Main {
    public static String longestPalindrome(String s) {
        String longest = "";
        for (int i = 0; i < s.length(); i++) {
            String odd = expandAroundCenter(s, i, i);
            String even = expandAroundCenter(s, i, i + 1);
            if (odd.length() > longest.length()) longest = odd;
            if (even.length() > longest.length()) longest = even;
        }
        return longest;
    }

    private static String expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("babad"));  // Output: 'bab' or 'aba'
    }
}

Finding the longest palindromic substring is a rewarding problem that deepens your understanding of string manipulation and algorithmic thinking. With multiple approaches, you can choose the method that balances simplicity and performance based on your needs.

Coding Clutch Challenge Series 101 – All Coding Challenges

FAQs

1. Can the problem be solved recursively?
   Yes, but it’s less efficient than iterative methods.
2. What if the input has multiple longest palindromes?
   Any valid result is acceptable.
3. How does the center expansion method work?
   It treats each character (and pair of characters) as the center and expands outward.
4. Are there libraries for solving this?
   Yes, some languages have built-in functions to find palindromes.
5. What are similar problems to practice?
   Try “Longest Substring without Repeating Characters” or “Longest Common Subsequence.”

Coding Clutch Challenge Series 101 – All Coding Challenges