Shortest Palindrome

Shortest Palindrome

LeetCode Problem

• Problem Number: 214
• Problem Link: https://leetcode.com/problems/shortest-palindrome/
• Difficulty: Hard
• Topics: String, Rolling Hash, String Matching, Hash Function

Problem Description

Given a string s, you can convert it to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

Note:

• A palindrome is a string that reads the same forward and backward
• You can only add characters to the front of the string

Examples

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints

• 0 <= s.length <= 5 * 10⁴
• s consists of lowercase English letters only