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
Method 1 ( Brute Force ) <\/strong> Time complexity: O ( n^3 ) Method 2 ( Dynamic Programming ) <\/strong> Output :<\/strong><\/p>\n Time complexity: O ( n^2 ) Longest Palindromic Substring – 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}]}}
\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
\nAuxiliary complexity: O ( 1 )<\/p>\n
\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[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20A%20dynamic%20programming%20solution%20for%20longest%20palindr.%0A%2F%2F%20This%20code%20is%20adopted%20from%20following%20link%0A%2F%2F%20http%3A%2F%2Fwww.leetcode.com%2F2011%2F11%2Flongest-palindromic-substring-part-i.html%0A%20%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstring.h%3E%0A%20%0A%2F%2F%20A%20utility%20function%20to%20print%20a%20substring%20str%5Blow..high%5D%0Avoid%20printSubStr(%20char*%20str%2C%20int%20low%2C%20int%20high%20)%0A%7B%0A%20%20%20%20for(%20int%20i%20%3D%20low%3B%20i%20%3C%3D%20high%3B%20%2B%2Bi%20)%0A%20%20%20%20%20%20%20%20printf(%22%25c%22%2C%20str%5Bi%5D)%3B%0A%7D%0A%20%0A%2F%2F%20This%20function%20prints%20the%20longest%20palindrome%20substring%0A%2F%2F%20of%20str%5B%5D.%0A%2F%2F%20It%20also%20returns%20the%20length%20of%20the%20longest%20palindrome%0Aint%20longestPalSubstr(%20char%20*str%20)%0A%7B%0A%20%20%20%20int%20n%20%3D%20strlen(%20str%20)%3B%20%2F%2F%20get%20length%20of%20input%20string%0A%20%0A%20%20%20%20%2F%2F%20table%5Bi%5D%5Bj%5D%20will%20be%20false%20if%20substring%20str%5Bi..j%5D%0A%20%20%20%20%2F%2F%20is%20not%20palindrome.%0A%20%20%20%20%2F%2F%20Else%20table%5Bi%5D%5Bj%5D%20will%20be%20true%0A%20%20%20%20bool%20table%5Bn%5D%5Bn%5D%3B%0A%20%20%20%20memset(table%2C%200%2C%20sizeof(table))%3B%0A%20%0A%20%20%20%20%2F%2F%20All%20substrings%20of%20length%201%20are%20palindromes%0A%20%20%20%20int%20maxLength%20%3D%201%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20table%5Bi%5D%5Bi%5D%20%3D%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20check%20for%20sub-string%20of%20length%202.%0A%20%20%20%20int%20start%20%3D%200%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n-1%3B%20%2B%2Bi)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(str%5Bi%5D%20%3D%3D%20str%5Bi%2B1%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20table%5Bi%5D%5Bi%2B1%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20start%20%3D%20i%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20maxLength%20%3D%202%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Check%20for%20lengths%20greater%20than%202.%20k%20is%20length%0A%20%20%20%20%2F%2F%20of%20substring%0A%20%20%20%20for%20(int%20k%20%3D%203%3B%20k%20%3C%3D%20n%3B%20%2B%2Bk)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Fix%20the%20starting%20index%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n-k%2B1%20%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Get%20the%20ending%20index%20of%20substring%20from%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20starting%20index%20i%20and%20length%20k%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20j%20%3D%20i%20%2B%20k%20-%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20checking%20for%20sub-string%20from%20ith%20index%20to%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20jth%20index%20iff%20str%5Bi%2B1%5D%20to%20str%5Bj-1%5D%20is%20a%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20palindrome%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(table%5Bi%2B1%5D%5Bj-1%5D%20%26%26%20str%5Bi%5D%20%3D%3D%20str%5Bj%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20table%5Bi%5D%5Bj%5D%20%3D%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(k%20%3E%20maxLength)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20start%20%3D%20i%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20maxLength%20%3D%20k%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20printf(%22Longest%20palindrome%20substring%20is%3A%20%22)%3B%0A%20%20%20%20printSubStr(%20str%2C%20start%2C%20start%20%2B%20maxLength%20-%201%20)%3B%0A%20%0A%20%20%20%20return%20maxLength%3B%20%2F%2F%20return%20length%20of%20LPS%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20char%20str%5B%5D%20%3D%20%22forgeeksskeegfor%22%3B%0A%20%20%20%20printf(%22%5CnLength%20is%3A%20%25d%5Cn%22%2C%20longestPalSubstr(%20str%20)%20)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\nLongest palindrome substring is: geeksskeeg\r\nLength is: 10<\/pre>\n
\nAuxiliary Space: O ( n^2 )<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"