# Solving Leetcode Interviews in Seconds with AI: Shortest Palindrome


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "214" 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
	> You are given a string s. You can convert s to a palindrome by adding characters in front of it. Return the shortest palindrome you can find by performing this transformation.   Example 1: Input: s = "aacecaaa" Output: "aaacecaaa" Example 2: Input: s = "abcd" Output: "dcbabcd"    Constraints:  0 <= s.length <= 5 * 104 s consists of lowercase English letters only.  

	# Explanation
	Here's the breakdown of the problem and an efficient solution:

*   **KMP-based Palindrome Extension:** The core idea is to find the longest prefix of the input string `s` that is also a suffix of the reversed string `s[::-1]`. This is efficiently done using a modified Knuth-Morris-Pratt (KMP) algorithm.

*   **Construct the LPS Array:**  We create a new string `combined = s + "#" + s[::-1]` and compute the longest proper prefix which is also a suffix (LPS) array for this combined string. The last element of the LPS array tells us the length of the longest prefix of `s` that is a suffix of `s[::-1]`.

*   **Build the Shortest Palindrome:**  We take the substring of the reversed string `s[::-1]` from index 0 up to the length of the input string minus the value obtained from the LPS array. We add this substring to the beginning of the original string `s` to generate the shortest palindrome.

*   **Time and Space Complexity:**
    *   Time Complexity: O(n), where n is the length of the input string s.
    *   Space Complexity: O(n), due to the combined string and LPS array.

	
	# Code
	```python
	def shortestPalindrome(s: str) -> str:
    """
    Finds the shortest palindrome by adding characters in front of the input string.
    """
    n = len(s)
    combined = s + "#" + s[::-1]
    m = len(combined)

    lps = [0] * m
    length = 0  # Length of the previous longest prefix suffix
    i = 1

    while i < m:
        if combined[i] == combined[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

    prefix_to_add = s[::-1][:n - lps[m - 1]]
    return prefix_to_add + s
	```