{"id":3568,"date":"2024-04-12T05:58:50","date_gmt":"2024-04-12T05:58:50","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=3568"},"modified":"2025-04-04T08:12:06","modified_gmt":"2025-04-04T08:12:06","slug":"shortest-palindrome-problem","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/shortest-palindrome-problem\/","title":{"rendered":"Shortest Palindrome Problem ( C++, JAVA, Python)"},"content":{"rendered":"\n

Palindrome-related questions are generally asked in interviews because they require a strong understanding of string manipulation and recursion. A palindrome is a string that is the same as if you reverse that string. For example, string s = \u201cabcba\u201d is a palindrome string read as from front and backward. One of the most common coding problems is \u201cshortest palindrome\u201d, which we are going to solve here.<\/p>\n\n\n\n

What is The \u201cShortest Palindrome\u201d Problem?<\/strong><\/h2>\n\n\n\n

As the name suggests, in the Shortest Palindrome problem, you are given a string, and you have to find the shortest Palindrome string from the given string by adding characters in the front. <\/strong><\/p>\n\n\n\n

For example, s = \u201cabac\u201d here you have to add \u2018c\u2019 at the front of the string to make it palindrome. So the resultant string would be res = \u201ccabac\u201d.The string x = \u201ccabaabac\u201d is also plainrom, but its size is not minimum, so it is not the shortest palindrome of the string s.<\/p>\n\n\n\n

Brute Force Approach<\/strong><\/h2>\n\n\n\n

Let’s start with Brute Force. In this approach, we will create all the possible substrings of index 0. We find out the longest substring starting from index 0 which is palindrome. After finding it, we find the substring of size  (n – size of longest substring). Starting from the size of the longest substring. We will reverse the resultant substring and add this to our main string. <\/p>\n\n\n\n

Let\u2019s examine this approach step by step.<\/p>\n\n\n\n

    \n
  1. Create two variables j = n-1  and curr = n-1. They will take care of the current index, where n is the size of the string.<\/li>\n\n\n\n
  2. Iterate over the string from i = 0 to i< n\/2. Now check if s[i] == s[j] or not.<\/li>\n\n\n\n
  3. If not, then update j =  curr – 1, curr = j, i = 0. And start repeating the same process.<\/li>\n\n\n\n
  4. If s[i] == s[j], then update j = j-1 and continue the process.<\/li>\n\n\n\n
  5. Once we have completed the loop, we will create a reverse string rev = reverse of s. Now find the substring from the string rev. <\/li>\n\n\n\n
  6. The substring will start from index 0 and of length (n-curr).<\/li>\n\n\n\n
  7. Now, we will add this substring to string s and return this new string.<\/li>\n\n\n\n
  8. <\/li>\n<\/ol>\n\n\n\n

    The time complexity for the above code is O(n^2) as we are finding all the substrings starting from index 0. It will take O(n^2) time. The space complexity is O(1) as we are not using any extra space.<\/p>\n\n\n\n

    Optimized Approach<\/strong><\/h2>\n\n\n\n

    In the above approach, we are taking too much time. We can reduce it if we use the KMP algorithm<\/a> here. The basic idea is that we will find the longest palindromic prefix. We will find this by adding \u2018#\u2019 and the reverse string of the given string to the back of the given string. Now, we’ll find the longest palindromic substring.<\/p>\n\n\n\n

    Let\u2019s examine this approach step by step.<\/p>\n\n\n\n

      \n
    1. First, create a reverse string of the given string. Now create another string having value s + \u2018#\u2019 + reverse of s.<\/li>\n\n\n\n
    2. Now call the function longest_prefix by passing this newly created string. <\/li>\n\n\n\n
    3. Inside the function, you need to create a vector v that will store the longest prefix for each index. Assign this with 0. Create a length variable that will keep track of the previous longest prefix length.<\/li>\n\n\n\n
    4. Now call the while loop and keep on iterating till i<n.<\/li>\n\n\n\n
    5. Now check if s[length] == s[i]. If it is, then update v[i++] == ++lenght. <\/li>\n\n\n\n
    6. If it is not then check if the length is 0 or not. If it is not 0, then update length = v[length-1]. If the length is 0, then update v[i++] = 0.<\/li>\n\n\n\n
    7. At last return v[n-1].<\/li>\n<\/ol>\n\n\n\n

      Let’s do in our favorite programming languages.<\/p>\n\n\n\n

      C++ Code<\/strong><\/h3>\n\n\n\n

      Here is the C++ solution to the shortest palindrome problem:<\/p>\n\n\n\n

      #include<bits\/stdc++.h>\n\nusing namespace std;\n\nint longest_prefix(string& s)\n\n{\n\nint n = s.length();\n\nvector<int> v(n, 0); \/\/ initialized with 0\n\nint length = 0; \/\/ length of previous longest prefix suffix\n\n\/\/ the loop calculates v[i] for i = 1 to M-1\n\nint i = 1;\n\nwhile (i < n) {\n\nif (s[length] == s[i]) {\n\nv[i++] = ++length;\n\n}\n\nelse {\n\nif (length != 0)\n\nlength = v[length - 1];\n\nelse\n\nv[i++] = 0;\n\n}\n\n}\n\nreturn v[n - 1];\n\n}\n\nint main(){\n\n\u00a0\u00a0\u00a0\u00a0string s = "abvbakjjka";\n\n\u00a0\u00a0\u00a0\u00a0string rev = s;\n\n\u00a0\u00a0\u00a0\u00a0reverse(rev.begin(),rev.end());\n\n\u00a0\u00a0\u00a0\u00a0string temp = s + '#' + rev;\n\n\u00a0\u00a0\u00a0\u00a0int len = longest_prefix(temp);\n\n\u00a0\u00a0\u00a0\u00a0int n = s.size();\n\n\u00a0\u00a0\u00a0\u00a0string res = rev.substr(0, n - len);\n\n\u00a0\u00a0\u00a0\u00a0res = res + s;\n\n\u00a0\u00a0\u00a0\u00a0cout<<res<<endl;\n\n\u00a0\u00a0\u00a0\u00a0return 0;\n\n}<\/pre><\/div>\n\n\n\n
      Java Code<\/strong><\/h3>\n\n\n\n
      Let’s solve it in Java too:<\/p>\n\n\n\n
      import java.util.*;\n\npublic class Main {\n\n\u00a0\u00a0\u00a0\u00a0static int longestPrefix(String s) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int n = s.length();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int[] v = new int[n]; \/\/ initialized with 0\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int length = 0; \/\/ length of previous longest prefix suffix\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ the loop calculates v[i] for i = 1 to M-1\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int i = 1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0while (i < n) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (s.charAt(length) == s.charAt(i)) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0v[i++] = ++length;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0} else {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (length != 0)\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0length = v[length - 1];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0v[i++] = 0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return v[n - 1];\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0public static void main(String[] args) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0String s = "abvbakjjka";\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0StringBuilder rev = new StringBuilder(s);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0rev.reverse();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0String temp = s + '#' + rev;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int len = longestPrefix(temp);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int n = s.length();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0String res = rev.substring(0, n - len) + s;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0System.out.println(res);\n\n\u00a0\u00a0\u00a0\u00a0}\n\n}<\/pre><\/div>\n\n\n\n
      Python Code<\/strong><\/h3>\n\n\n\n
      Here is the same implementation in Python:<\/p>\n\n\n\n
      def longest_prefix(s):\n\n\u00a0\u00a0\u00a0\u00a0n = len(s)\n\n\u00a0\u00a0\u00a0\u00a0v = [0] * n\u00a0 # initialized with 0\n\n\u00a0\u00a0\u00a0\u00a0length = 0\u00a0 # length of previous longest prefix suffix\n\n\u00a0\u00a0\u00a0\u00a0# the loop calculates v[i] for i = 1 to M-1\n\n\u00a0\u00a0\u00a0\u00a0i = 1\n\n\u00a0\u00a0\u00a0\u00a0while i < n:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if s[length] == s[i]:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0v[i] = length + 1\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0length += 1\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0i += 1\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if length != 0:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0length = v[length - 1]\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0v[i] = 0\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0i += 1\n\n\u00a0\u00a0\u00a0\u00a0return v[n - 1]\n\nif __name__ == "__main__":\n\n\u00a0\u00a0\u00a0\u00a0s = "abvbakjjka"\n\n\u00a0\u00a0\u00a0\u00a0rev = s[::-1]\n\n\u00a0\u00a0\u00a0\u00a0temp = s + '#' + rev\n\n\u00a0\u00a0\u00a0\u00a0length = longest_prefix(temp)\n\n\u00a0\u00a0\u00a0\u00a0n = len(s)\n\n\u00a0\u00a0\u00a0\u00a0res = rev[:n - length] + s\n\n\u00a0\u00a0\u00a0\u00a0print(res)<\/pre><\/div>\n\n\n\n
      Output:<\/strong> <\/p>\n\n\n\n
      akjjkabvbakjjka<\/code><\/pre>\n\n\n\n
      The time complexity for the above code is O(n) as we are just iterating the string once. The space complexity for the above code is O(n) as we are using a vector of size n.<\/p>\n\n\n\n
      Analysis of Both Approaches <\/strong><\/h3>\n\n\n\n
      Approach<\/strong><\/th>Time Complexity<\/strong><\/th>Space Complexity<\/strong><\/th>Description<\/strong><\/th><\/tr><\/thead>
      Brute Force<\/td>O( n^2 )<\/td>O(1)<\/td>As we are finding all the substrings starting from index 0, whose time complexity is O(n^2)<\/td><\/tr>
      Optimized Approach<\/td>O(n)<\/td>O(n)<\/td>We are just storing the values of the longest prefix from each index in a vector and because of this, the space complexity goes to O(n).<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
      Conclusion<\/strong><\/h2>\n\n\n\n
      In this article, we discussed various approaches to solving the \u201cShortest Palindrome\u201d question. We have seen that the brute force approach is taking O(n^2) time complexity as we are finding all the substring that starts from index 0.  We also see how we can optimize the above approach by storing the longest prefix for all the indexes. You can also try some more questions like \u201cLongest Palindromic Substring<\/a>,\u201d and \u201cMaximum Deletions on a String<\/a>\u201d etc.<\/p>\n","protected":false},"excerpt":{"rendered":"
      Palindrome-related questions are generally asked in interviews because they require a strong understanding of string manipulation and recursion. A palindrome is a string that is the same as if you reverse that string. For example, string s = \u201cabcba\u201d is a palindrome string read as from front and backward. One of the most common coding […]<\/p>\n","protected":false},"author":14,"featured_media":3612,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,176,15],"class_list":["post-3568","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-kmp","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/3568","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=3568"}],"version-history":[{"count":5,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/3568\/revisions"}],"predecessor-version":[{"id":7371,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/3568\/revisions\/7371"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/3612"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=3568"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=3568"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=3568"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}