{"id":26830,"date":"2017-12-24T15:39:19","date_gmt":"2017-12-24T10:09:19","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26830"},"modified":"2017-12-24T15:44:12","modified_gmt":"2017-12-24T10:14:12","slug":"longest-palindromic-substring","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/longest-palindromic-substring\/","title":{"rendered":"Longest Palindromic Substring"},"content":{"rendered":"<p>Given a string, find the longest substring which is palindrome. For example, if the given string is \u201cforwikitechyyhcetikiwrof\u201d, the output should be \u201cwikitechyyhcetikiw\u201d.<\/p>\n<p><strong>Method 1 ( Brute Force ) <\/strong><br \/>\nThe simple approach is to check each substring whether the substring is a palindrome or not. We can run three loops, the outer two loops pick all substrings one by one by fixing the corner characters, the inner loop checks whether the picked substring is palindrome or not.<\/p>\n<p>Time complexity: O ( n^3 )<br \/>\nAuxiliary complexity: O ( 1 )<\/p>\n<p><strong>Method 2 ( Dynamic Programming ) <\/strong><br \/>\nThe time complexity can be reduced by storing results of subproblems. The idea is similar to this post. We maintain a boolean table[n][n] that is filled in bottom up manner. The value of table[i][j] is true, if the substring is palindrome, otherwise false. To calculate table[i][j], we first check the value of table[i+1][j-1], if the value is true and str[i] is same as str[j], then we make table[i][j] true. Otherwise, the value of table[i][j] is made false.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">C<\/span> <\/div> <pre class=\"language-c code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-c code-embed-code\">\/\/ A dynamic programming solution for longest palindr.<br\/>\/\/ This code is adopted from following link<br\/>\/\/ http:\/\/www.leetcode.com\/2011\/11\/longest-palindromic-substring-part-i.html<br\/> <br\/>#include &lt;stdio.h&gt;<br\/>#include &lt;string.h&gt;<br\/> <br\/>\/\/ A utility function to print a substring str[low..high]<br\/>void printSubStr( char* str, int low, int high )<br\/>{<br\/>    for( int i = low; i &lt;= high; ++i )<br\/>        printf(&quot;%c&quot;, str[i]);<br\/>}<br\/> <br\/>\/\/ This function prints the longest palindrome substring<br\/>\/\/ of str[].<br\/>\/\/ It also returns the length of the longest palindrome<br\/>int longestPalSubstr( char *str )<br\/>{<br\/>    int n = strlen( str ); \/\/ get length of input string<br\/> <br\/>    \/\/ table[i][j] will be false if substring str[i..j]<br\/>    \/\/ is not palindrome.<br\/>    \/\/ Else table[i][j] will be true<br\/>    bool table[n][n];<br\/>    memset(table, 0, sizeof(table));<br\/> <br\/>    \/\/ All substrings of length 1 are palindromes<br\/>    int maxLength = 1;<br\/>    for (int i = 0; i &lt; n; ++i)<br\/>        table[i][i] = true;<br\/> <br\/>    \/\/ check for sub-string of length 2.<br\/>    int start = 0;<br\/>    for (int i = 0; i &lt; n-1; ++i)<br\/>    {<br\/>        if (str[i] == str[i+1])<br\/>        {<br\/>            table[i][i+1] = true;<br\/>            start = i;<br\/>            maxLength = 2;<br\/>        }<br\/>    }<br\/> <br\/>    \/\/ Check for lengths greater than 2. k is length<br\/>    \/\/ of substring<br\/>    for (int k = 3; k &lt;= n; ++k)<br\/>    {<br\/>        \/\/ Fix the starting index<br\/>        for (int i = 0; i &lt; n-k+1 ; ++i)<br\/>        {<br\/>            \/\/ Get the ending index of substring from<br\/>            \/\/ starting index i and length k<br\/>            int j = i + k - 1;<br\/> <br\/>            \/\/ checking for sub-string from ith index to<br\/>            \/\/ jth index iff str[i+1] to str[j-1] is a<br\/>            \/\/ palindrome<br\/>            if (table[i+1][j-1] &amp;&amp; str[i] == str[j])<br\/>            {<br\/>                table[i][j] = true;<br\/> <br\/>                if (k &gt; maxLength)<br\/>                {<br\/>                    start = i;<br\/>                    maxLength = k;<br\/>                }<br\/>            }<br\/>        }<br\/>    }<br\/> <br\/>    printf(&quot;Longest palindrome substring is: &quot;);<br\/>    printSubStr( str, start, start + maxLength - 1 );<br\/> <br\/>    return maxLength; \/\/ return length of LPS<br\/>}<br\/> <br\/>\/\/ Driver program to test above functions<br\/>int main()<br\/>{<br\/>    char str[] = &quot;forgeeksskeegfor&quot;;<br\/>    printf(&quot;\\nLength is: %d\\n&quot;, longestPalSubstr( str ) );<br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\n<p><strong>Output :<\/strong><\/p>\n<pre>Longest palindrome substring is: geeksskeeg\r\nLength is: 10<\/pre>\n<p>Time complexity: O ( n^2 )<br \/>\nAuxiliary Space: O ( n^2 )<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Longest Palindromic Substring &#8211; Dynamic Programming -Given a string,find the longest substring which is palindrome. For example, if the given string ing is<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,70145,83623],"tags":[7378,72847,72842,80090,72845,70483,72848,72840,72846,72994,72843,72992,72854,72844,72019,72850,72839,72029,80088,73558,73585,73562,73563,73584,73560,73583,73559,72016],"class_list":["post-26830","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-dynamic-programming","category-palindrome-partitioning","tag-c-string","tag-concept-of-dynamic-programming","tag-define-dynamic-programming","tag-define-palindrome","tag-definition-of-dynamic-programming","tag-dynamic-programming","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-in-data-structure","tag-dynamic-programming-in-python","tag-dynamic-programming-problems","tag-dynamic-programming-python","tag-dynamic-programming-set-1","tag-dynamic-programming-software","tag-examples-of-palindromes","tag-explain-dynamic-programming","tag-how-to-solve-dynamic-programming-problems","tag-long-palindrome","tag-longest-english-palindrome","tag-longest-palindrome","tag-longest-palindrome-algorithm","tag-longest-palindrome-in-a-string","tag-longest-palindrome-word","tag-longest-palindromes","tag-longest-palindromic-subsequence","tag-longest-palindromic-substring","tag-manachers-algorithm","tag-palindrome"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26830","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26830"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26830\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26830"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26830"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26830"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}