# Solving Leetcode Interviews in Seconds with AI: Longest Palindromic Substring


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "5" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> Given a string s, return the longest palindromic substring in s.   Example 1:  Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.  Example 2:  Input: s = "cbbd" Output: "bb"    Constraints:  1 <= s.length <= 1000 s consist of only digits and English letters.  

	# Explanation
	Here's a breakdown of the solution and the code:

*   **High-Level Approach:**
    *   **Dynamic Programming (DP):** Create a 2D boolean table `dp` where `dp[i][j]` indicates whether the substring `s[i:j+1]` is a palindrome.
    *   **Base Cases:** Initialize the table for single-character and two-character palindromes.
    *   **Iterative Expansion:** Build the `dp` table by checking longer substrings, leveraging previously computed results for smaller substrings.

*   **Complexity:**
    *   Runtime: O(n^2), where n is the length of the input string `s`.
    *   Storage: O(n^2) due to the `dp` table.

	
	# Code
	```python
	def longestPalindrome(s: str) -> str:
    """
    Finds the longest palindromic substring in the given string.

    Args:
        s: The input string.

    Returns:
        The longest palindromic substring.
    """

    n = len(s)
    if n < 1:
        return ""

    dp = [[False] * n for _ in range(n)]
    start = 0
    max_len = 1

    # Base case: Single-character palindromes
    for i in range(n):
        dp[i][i] = True

    # Base case: Two-character palindromes
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_len = 2

    # Check for longer palindromes
    for k in range(3, n + 1):  # Length of substring
        for i in range(n - k + 1):  # Starting index
            j = i + k - 1  # Ending index
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                if k > max_len:
                    start = i
                    max_len = k

    return s[start:start + max_len]
	```