Shortest Palindrome

                                            
class Solution {
public:
    string shortestPalindrome(string s) {
        string rev = s;
        reverse(rev.begin(), rev.end());
        
        string temp = s + "#" + rev;
        int n = temp.size();
        
        vector<int> lps(n, 0);
        
        for(int i = 1; i < n; i++){
            int j = lps[i - 1];
            while(j > 0 && temp[i] != temp[j]){
                j = lps[j - 1];
            }
            if(temp[i] == temp[j]){
                j++;
            }
            lps[i] = j;
        }
        
        return rev.substr(0, s.size() - lps[n - 1]) + s;
    }
};

                                            
class Solution {
    public String shortestPalindrome(String s) {
        int n = s.length();
        String rev = new StringBuilder(s).reverse().toString();
        for (int i = 0; i < n; i++) {
            if (s.substring(0, n - i).equals(rev.substring(i))) {
                return rev.substring(0, i) + s;
            }
        }
        return ""; // should never reach here
    }
}

                                            
class Solution(object):
    def shortestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        rev_s = s[::-1]
        for i in range(len(s)+1):
            if s.startswith(rev_s[i:]):
                return rev_s[:i] + s

                                            
public class Solution {
    public string ShortestPalindrome(string s) {
        if (s.Length == 0) return s;
        
        string rev = new string(s.Reverse().ToArray());
        string comb = s + "#" + rev;
        
        int[] lps = new int[comb.Length];
        int len = 0, i = 1;
        
        while (i < comb.Length) {
            if (comb[i] == comb[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        int toAdd = s.Length - lps[comb.Length - 1];
        string suffix = rev.Substring(0, toAdd);
        
        return suffix + s;
    }
}

                                            
/**
 * @param {string} s
 * @return {string}
 */
var shortestPalindrome = function(s) {
    const reversed = s.split('').reverse().join('');
    const l = s + '#' + reversed;
    const p = new Array(l.length).fill(0);
    for (let i = 1; i < l.length; i++) {
        let j = p[i - 1];
        while (j > 0 && l[i] !== l[j]) {
            j = p[j - 1];
        }
        p[i] = j + (l[i] === l[j] ? 1 : 0);
    }
    return reversed.slice(0, s.length - p[l.length - 1]) + s;
};

                                            
function shortestPalindrome(s: string): string {
    const reversed = s.split('').reverse().join('');
    const full = s + '#' + reversed;
    const lps = new Array(full.length).fill(0);
    
    for (let i = 1; i < full.length; i++) {
        let j = lps[i - 1];
        while (j > 0 && full[i] !== full[j]) {
            j = lps[j - 1];
        }
        lps[i] = j + (full[i] === full[j] ? 1 : 0);
    }
    
    return reversed.slice(0, s.length - lps[full.length - 1]) + s;
};

                                            
class Solution {
    /**
     * @param String $s
     * @return String
     */
    function shortestPalindrome($s) {
        $rev = strrev($s);
        $n = strlen($s);
        for ($i = 0; $i < $n; $i++) {
            if (substr($s, 0, $n - $i) == substr($rev, $i)) {
                return substr($rev, 0, $i) . $s;
            }
        }
        return '';
    }
}

                                            
class Solution {
    func shortestPalindrome(_ s: String) -> String {
        guard !s.isEmpty else { return "" }
        var rev = String(s.reversed())
        var i = 0
        while !s.hasPrefix(rev.suffix(s.count - i)) {
            i += 1
        }
        return String(rev.prefix(i)) + s
    }
}

                                            
class Solution {
    fun shortestPalindrome(s: String): String {
        val rev = s.reversed()
        for (i in s.indices) {
            if (s.startsWith(rev.substring(i))) {
                return rev.substring(0, i) + s
            }
        }
        return ""
    }
}

                                            
class Solution {
  String shortestPalindrome(String s) {
    String rev = s.split('').reversed.join();
    String temp = s + '#' + rev;
    List<int> lps = List.filled(temp.length, 0);
    
    for (int i = 1; i < temp.length; i++) {
      int j = lps[i - 1];
      while (j > 0 && temp[i] != temp[j]) {
        j = lps[j - 1];
      }
      if (temp[i] == temp[j]) {
        j++;
      }
      lps[i] = j;
    }
    
    return rev.substring(0, s.length - lps[temp.length - 1]) + s;
  }
}

                                            
func shortestPalindrome(s string) string {
    if len(s) <= 1 {
        return s
    }
    
    for i := len(s); i >= 0; i-- {
        if isPalindrome(s[:i]) {
            return reverse(s[i:]) + s
        }
    }
    
    return ""
}

func isPalindrome(s string) bool {
    left, right := 0, len(s)-1
    for left < right {
        if s[left] != s[right] {
            return false
        }
        left++
        right--
    }
    return true
}

func reverse(s string) string {
    runes := []rune(s)
    for left, right := 0, len(runes)-1; left < right; left, right = left+1, right-1 {
        runes[left], runes[right] = runes[right], runes[left]
    }
    return string(runes)
}

                                            
# @param {String} s
# @return {String}
def shortest_palindrome(s)
    i = 0
    for j in (s.length - 1).downto(0)
        if s[i] == s[j]
            i += 1
        end
    end
    if i == s.length
        return s
    end
    return s[i..-1].reverse + shortest_palindrome(s[0...i]) + s[i..-1]
end

To solve this coding challenge, we need to convert a given string

s

into the shortest possible palindrome by adding characters only in front of it. A palindrome reads the same forward and backward. The goal is to achieve this with the minimum number of additional characters.

Explanation

Firstly, we need to understand that the most straightforward way to make a string a palindrome is by appending the reverse of the string to its start. However, this approach often leads to longer strings than necessary. Instead, we should look for the longest palindromic prefix in the string and then append the minimum number of characters needed to make the entire string a palindrome. The trick lies in determining the longest prefix of

s

which is also a palindrome. Once we identify such a prefix, the remaining part of the string (which is not part of the palindrome prefix) is reversed and added to the front to form the required palindrome. Here is the step-by-step detailed methodology to solve this:

Reverse the String : First, reverse the given string
s

to get
rev_s

.
Identify Longest Palindromic Prefix : Iterate through each character in the string and see if the prefix of
s

starting from the character equals the corresponding suffix in
rev_s

.
Construct Result : The characters in
rev_s

that do not match the prefix part will be added before
s

.

Let us translate this methodology into pseudocode:

Detailed Steps in Pseudocode:

Initialize Variables :

rev_s

= reverse of
s
i

= loop index initialized to 0

Find Longest Palindromic Prefix :

Loop from
i = 0

to
len(s)

If the substring of
s

from the beginning to the end corresponds to the substring of
rev_s

from
i

to end:

Identify this as the longest palindromic prefix

Construct Shortest Palindrome :

The characters from the start of
rev_s

up to
i

(those outside the palindromic prefix) are added before
s

.

Pseudocode with Comments:

                                            
# Start by reversing the input string
reverse_string = reverse(s)

# Initialize a variable to hold the longest palindromic prefix found
longest_palindromic_prefix_length = 0

# Loop through the string to find the longest palindromic prefix
for i from 0 to length(s):
    # Check if the substring from the current position to the end is a prefix in the original string
    if s starts with substring(reverse_string from index i to end):
        # Set the palindromic prefix length
        longest_palindromic_prefix_length = i
        # Break the loop as we found the longest possible prefix
        break

# The result will be the unmatched part in reverse followed by the original string
shortest_palindrome = substring(reverse_string from start to longest_palindromic_prefix_length) + s

# Return the shortest palindrome
return shortest_palindrome

To break this down further:

Reverse the string
s

: This will help to quickly compare suffixes of the reverse with prefixes of the original string.
Find the matching prefix : By slicing and comparing the original and reversed string, we can find the longest prefix which is already a palindrome.
Construct the result string : Append the part of the reversed string which does not match the palindromic prefix found to the start of the original string.

This process ensures that we add the minimum number of characters required and achieve the shortest palindrome possible, thereby solving the given challenge efficiently.