🟡 String Algorithms: Longest Palindromic Substring

[stemaway]

---

String Algorithms: Longest Palindromic Substring

Difficulty: Medium

---

Problem Statement

Given a string s, find the longest palindromic substring in s.

---

Implementation Details

Implement the following function:

def longest_palindrome(s: str) -> str:
    """
    Find the longest palindromic substring in s.

    Args:
        s (str): The input string.

    Returns:
        str: The longest palindromic substring.
    """
    pass  # Your implementation here

Constraints

• String Length: (1 \leq \text{len(s)} \leq 10^3)
• String Content: s consists of only digits and English letters.

---

Example Usage

s = "babad"
print(longest_palindrome(s))  # Expected Output: "bab" or "aba"

s = "cbbd"
print(longest_palindrome(s))  # Expected Output: "bb"

---

Test Cases

def test_longest_palindrome():
    # Test Case 1: Palindrome in the middle
    assert longest_palindrome("babad") in ("bab", "aba")

    # Test Case 2: Even length palindrome
    assert longest_palindrome("cbbd") == "bb"

    # Test Case 3: Single character
    assert longest_palindrome("a") == "a"

    # Test Case 4: Entire string is palindrome
    assert longest_palindrome("racecar") == "racecar"

    # Test Case 5: Multiple palindromes
    assert longest_palindrome("forgeeksskeegfor") == "geeksskeeg"

    # Test Case 6: No repeating characters
    assert longest_palindrome("abcde") == "a"  # Any single character

    # Test Case 7: Palindrome at the end
    assert longest_palindrome("abacab") == "bacab"

    print("All test cases pass!")

---

Expected Solution Approach

To find the longest palindromic substring, expand around possible centers.

Algorithm Steps

1. Iterate Over the String:

   • For each index i in the string:
     • Odd Length Palindromes:
       • Expand around center i.
     • Even Length Palindromes:
       • Expand around centers i and i+1.

2. Expand Around Centers:

   • While the characters at left and right indices are the same, expand outward.
   • Keep track of the maximum length and starting index of the longest palindrome found.

3. Return the Longest Palindrome:

   • Extract the substring using the starting index and maximum length.

Time Complexity

• Time Complexity: (O(N^2)), where (N) is the length of the string.
• Space Complexity: (O(1))

Optimizations

• For large inputs, Manacher’s Algorithm can be used to achieve (O(N)) time complexity, but it’s complex and beyond the scope of this problem.

---

Implementation Hint

Here’s a skeleton to help you start:

def longest_palindrome(s: str) -> str:
    if not s:
        return ""

    start = 0
    max_length = 1

    for i in range(len(s)):
        # Odd length palindrome
        l, r = i, i
        while l >=0 and r < len(s) and s[l] == s[r]:
            if (r - l +1) > max_length:
                start = l
                max_length = r - l +1
            l -=1
            r +=1

        # Even length palindrome
        l, r = i, i+1
        while l >=0 and r < len(s) and s[l] == s[r]:
            if (r - l +1) > max_length:
                start = l
                max_length = r - l +1
            l -=1
            r +=1

    return s[start:start+max_length]

---

Learning Objectives

1. Understand String Manipulation Techniques:

   • Implement algorithms that require character-level analysis.
   • Handle both odd and even length palindromes.

2. Optimize Nested Loops:

   • Avoid unnecessary computations by expanding only when characters match.
   • Recognize when to stop expansion.

3. Handle Edge Cases in Strings:

   • Manage single-character strings.
   • Consider palindromes at different positions (start, middle, end).

4. Analyze Algorithm Complexity:

   • Balance simplicity and efficiency.
   • Understand the trade-offs of more complex algorithms for optimization.

---

Real-World Applications

• Data Compression: Identify repeating patterns in data sequences.
• DNA Sequencing: Find palindromic sequences that have biological significance.
• Text Analysis: Detect palindromic words or phrases in literature.
• Cybersecurity: Analyze patterns in encryption and decryption processes.

---