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, 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

    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