What is the time complexity of Shortest Palindrome?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Shortest Palindrome?

This problem uses String, Rolling Hash, String Matching, Hash Function. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Shortest Palindrome?

Insight 1: The shortest palindrome can be found by identifying the longest palindromic prefix of the given string 's'. Insight 2: The KMP algorithm's longest proper prefix which is also a suffix (LPS) array computation can be adapted to find the longest palindromic prefix.

Which companies ask LeetCode 214. Shortest Palindrome in interviews?

This problem is frequently asked at Accenture, Google, Pocket Gems, Visa, eBay.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Shortest Palindrome - LeetCode 214 Solution

Q: How to solve Shortest Palindrome?

The solution leverages the concept of finding the longest palindromic prefix of the input string 's'. It constructs a new string 'temp_s' by concatenating 's', a delimiter '#', and the reverse of 's'. Then, it computes the LPS (Longest Proper Prefix which is also a Suffix) array for 'temp_s' using a modified KMP algorithm. The last element of the LPS array indicates the length of the longest palindromic prefix of 's'. Finally, the solution constructs the shortest palindrome by reversing the suffix of 's' (the part that's not part of the longest palindromic prefix) and prepending it to the original string 's'.

Shortest Palindrome - Complete Solution Guide

Shortest Palindrome is LeetCode problem 214, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 * 10 4 s consists of lowercase English letters only.

Detailed Explanation

The problem asks us to find the shortest palindrome that can be formed by adding characters to the beginning of a given string 's'. The goal is to return this shortest palindrome.

Solution Approach

The solution leverages the concept of finding the longest palindromic prefix of the input string 's'. It constructs a new string 'temp_s' by concatenating 's', a delimiter '#', and the reverse of 's'. Then, it computes the LPS (Longest Proper Prefix which is also a Suffix) array for 'temp_s' using a modified KMP algorithm. The last element of the LPS array indicates the length of the longest palindromic prefix of 's'. Finally, the solution constructs the shortest palindrome by reversing the suffix of 's' (the part that's not part of the longest palindromic prefix) and prepending it to the original string 's'.

Step-by-Step Algorithm

Step 1: Reverse the input string 's' and store it in 'rev_s'.
Step 2: Create a new string 'temp_s' by concatenating 's', a delimiter '#', and 'rev_s'. The '#' character is crucial to avoid incorrect LPS calculations.
Step 3: Compute the LPS array for 'temp_s'. The LPS array at index i stores the length of the longest proper prefix of temp_s[0...i] which is also a suffix of temp_s[0...i].
Step 4: The last element of the LPS array represents the length of the longest palindromic prefix of the original string 's'.
Step 5: Extract the suffix of 's' that is not part of the longest palindromic prefix.
Step 6: Reverse the extracted suffix.
Step 7: Prepend the reversed suffix to the original string 's' to create the shortest palindrome.

Key Insights

Insight 1: The shortest palindrome can be found by identifying the longest palindromic prefix of the given string 's'.
Insight 2: The KMP algorithm's longest proper prefix which is also a suffix (LPS) array computation can be adapted to find the longest palindromic prefix.
Insight 3: By concatenating the original string 's', a special character '#', and the reversed string of 's', we can use the LPS array to find the length of the longest palindromic prefix of 's'.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: String, Rolling Hash, String Matching, Hash Function.

Companies

Asked at: Accenture, Google, Pocket Gems, Visa, eBay.

Shortest Palindrome | LeetCode 214

Hard

String Rolling Hash String Matching Hash Function

Time: O(n)Space: O(n)

Solution Code

Available in:

class Solution {
    public String shortestPalindrome(String s) {
        int n = s.length();
        if (n <= 1) {
            return s;
        }
        
        String rev_s = new StringBuilder(s).reverse().toString();
        String temp_s = s + '#' + rev_s;
        
        int m = temp_s.length();
        int[] lps = new int[m];
        
        int length = 0;
        int i = 1;
        while (i < m) {
            if (temp_s.charAt(i) == temp_s.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        int len_lpp = lps[m - 1];
        
        return new StringBuilder(s.substring(len_lpp)).reverse().toString() + s;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 214: Shortest Palindrome - Detailed explanation and solution approaches.

Topics

String Rolling Hash String Matching Hash Function

Companies

AccentureGooglePocket GemsVisaeBay

Stats

Difficulty:Hard

Languages:4

Companies:5

Problem #:214

Problem Explanation

The problem asks us to find the shortest palindrome that can be formed by adding characters to the beginning of a given string 's'. The goal is to return this shortest palindrome.

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Reverse the input string 's' and store it in 'rev_s'.
2
Step 2: Create a new string 'temp_s' by concatenating 's', a delimiter '#', and 'rev_s'. The '#' character is crucial to avoid incorrect LPS calculations.
3
Step 3: Compute the LPS array for 'temp_s'. The LPS array at index i stores the length of the longest proper prefix of temp_s[0...i] which is also a suffix of temp_s[0...i].
4
Step 4: The last element of the LPS array represents the length of the longest palindromic prefix of the original string 's'.
5
Step 5: Extract the suffix of 's' that is not part of the longest palindromic prefix.
6
Step 6: Reverse the extracted suffix.
7
Step 7: Prepend the reversed suffix to the original string 's' to create the shortest palindrome.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is dominated by the KMP-style algorithm for computing the LPS array. This algorithm iterates through the 'temp_s' string once, resulting in O(n) time. The space complexity arises from storing the reversed string, the concatenated string, and the LPS array, all of which scale linearly with the length of the input string.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

For each prefix length of 's', check if reversing the remaining suffix and prepending it to 's' results in a palindrome. Find the smallest palindrome achievable.

Time: O(n^2)Space: O(n)

Trade-offs: Brute force is simple to understand, but its quadratic time complexity makes it inefficient for larger input strings. The provided solution using KMP is significantly faster.

Recursion

Recursively check if a string is a palindrome, if not, add the last character to the beginning and end and recursively check again.

Time: O(n^2)Space: O(n) - due to recursion stack.

Trade-offs: Recursion is easy to conceptually understand but also very inefficient and often results in stack overflow for bigger test cases.

✨

Key Insights

1Insight 1: The shortest palindrome can be found by identifying the longest palindromic prefix of the given string 's'.
2Insight 2: The KMP algorithm's longest proper prefix which is also a suffix (LPS) array computation can be adapted to find the longest palindromic prefix.
3Insight 3: By concatenating the original string 's', a special character '#', and the reversed string of 's', we can use the LPS array to find the length of the longest palindromic prefix of 's'.

📚

Key Terms Explained

For Students

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string. The code handles this by returning the empty string since n <= 1 triggers the return s statement.
Edge case 2: Single character string. The code correctly returns the original string as it's already a palindrome.
Edge case 3: A string that is already a palindrome. The algorithm still works correctly, as the reversed suffix will be an empty string, and the original string is returned.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting the '#' delimiter when constructing 'temp_s'. Without it, the LPS array might incorrectly identify non-palindromic prefixes as palindromic.

✗Common mistake 2: Incorrectly implementing the KMP algorithm for LPS array computation, leading to wrong LPS values and an incorrect shortest palindrome.

✗Common mistake 3: Not handling the edge cases of empty strings or single-character strings correctly.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Bioinformatics. Identifying palindromic sequences in DNA, which often have functional significance.

🏦Real-world scenario 2: Data compression. Palindrome detection can be used as a preprocessing step in data compression algorithms, as palindromic substrings can be efficiently represented.

🎮Real-world scenario 3: Text editing. Auto-completion features could use palindrome detection to suggest potential completions that result in palindromic phrases.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 5, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

❓

Frequently Asked Questions

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Shortest Palindrome"?

For this hard-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether rolling hash techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?