{"id":2301,"date":"2021-10-02T17:55:00","date_gmt":"2021-10-02T12:25:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2301"},"modified":"2022-08-16T10:41:27","modified_gmt":"2022-08-16T05:11:27","slug":"longest-palindromic-substring","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/longest-palindromic-substring\/","title":{"rendered":"Longest Palindromic Substring"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#simple-approach\">Simple Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#implementation-of-simple-approach\">Implementation of Simple Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#cc-implementation\">C\/C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><\/ul><li><a href=\"#efficient-approach-dynamic-programming\">Efficient Approach: Dynamic Programming<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#implementation-of-dp-approach\">Implementation of DP Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-dynamic-programming\">C++ Implementation: Dynamic Programming<\/a><\/li><li><a href=\"#-java-implementation-dynamic-programming\"><meta charset=\"utf-8\">Java Implementation: Dynamic Programming<\/a><\/li><li><a href=\"#python-implementation-dynamic-programming\">Python Implementation: Dynamic Programming<\/a><\/li><\/ul><\/ul><li><a href=\"#expand-around-center-approach\">Expand Around Center Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#dry-run-of-approach\">Dry Run of Approach<\/a><\/li><li><a href=\"#implementation-of-above-approach\">Implementation Of Above Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-of-expand-around-center-approach\">C++ Implementation of Expand Around Center Approach<\/a><\/li><li><a href=\"#java-implementation-of-expand-around-center-approach\">Java Implementation of Expand Around Center Approach<\/a><\/li><li><a href=\"#-python-implementation-of-expand-around-center-approach\"><meta charset=\"utf-8\">Python Implementation of Expand Around Center Approach<\/a><\/li><\/ul><\/ul><li><a href=\"#practice-questions\">Practice Questions<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a string, we have to find the longest palindromic substring(substring is a sequence of characters that is contiguous within a string. For example, the string &#8220;Interviewbit&#8221;, &#8220;er&#8221;, &#8220;view&#8221;, &#8220;bit&#8221;,\u2026etc are substrings, but not &#8220;tr&#8221; as both these characters are not continuous. Whereas palindrome is a word that reads the same backward as forwards. Examples include abba, zzzz, xyyx.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<p><strong>Input:<\/strong> findnitianhere<br><strong>Output:<\/strong> indni<br><strong>Explanation:<\/strong> Substring from index 1 to index 5 is the longest substring.<\/p>\n\n\n\n<p><strong>Input:<\/strong> \u201cacacacb\u201d<br><strong>Output:<\/strong> 5<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"408\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Example\"  class=\"wp-image-2307 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4-300x120.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4-768x306.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4-380x151.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4-550x219.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4-800x319.jpg 800w\" ><\/figure>\n\n\n\n<h2 id=\"simple-approach\">Simple Approach<\/h2>\n\n\n\n<p>The brute force solution which comes into our mind is to pick all the substrings from a string that is possible and then we will check whether that substring is a palindrome or not.<\/p>\n\n\n\n<p>Hence if we will talk about the implementation part of this approach then we just have to use two loops for finding all the substrings and then one more for checking whether the substance is a palindrome or not. Hence total time complexity of this approach will be N^3.<\/p>\n\n\n\n<h3 id=\"implementation-of-simple-approach\">Implementation of Simple Approach<\/h3>\n\n\n\n<h4 id=\"cc-implementation\"><span id=\"c-c-implementation\">C\/C++ Implementation<\/span><\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/e217b47b92fbb6de9219 title='Interviewbit Ide snippet\/e217b47b92fbb6de9219' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h4 id=\"java-implementation\">Java Implementation<\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/425accb4533a323030e0 title='Interviewbit Ide snippet\/425accb4533a323030e0' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h4 id=\"python-implementation\">Python Implementation<\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/1be7ff68f9deffda7c66 title='Interviewbit Ide snippet\/1be7ff68f9deffda7c66' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<p><strong>Time complexity:<\/strong> O(N^3), Where N is the size of the string.<br><strong>Space complexity:<\/strong> O(1)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"efficient-approach-dynamic-programming\">Efficient Approach: Dynamic Programming<\/h2>\n\n\n\n<p>We can find some patterns in validating palindromes to avoid unnecessary re-computation and improve the brute force approach by memorizing the data.<\/p>\n\n\n\n<p>Consider one example &#8220;cbebc&#8221;. If we already knew that &#8220;beb&#8221; is a palindrome, it is obvious that &#8220;cbebc&#8221; must be a palindrome since the two left and right end letters are the same.<\/p>\n\n\n\n<p>We define P(i,j) as follows<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"DP approach\"  class=\"wp-image-2308 pk-lazyload\"  width=\"573\"  height=\"218\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 573px) 100vw, 573px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-2.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-2.jpg 541w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-2-300x114.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-2-380x145.jpg 380w\" ><\/figure><\/div>\n\n\n\n<p>Therefore,<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"541\"  height=\"206\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Formula\"  class=\"wp-image-2311 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 541px) 100vw, 541px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-7.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-7.jpg 541w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-7-300x114.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-7-380x145.jpg 380w\" ><\/figure>\n\n\n\n<p>The base cases are,<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"541\"  height=\"264\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"DP approach 1\"  class=\"wp-image-2305 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 541px) 100vw, 541px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-4.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-4.jpg 541w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-4-300x146.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-4-380x185.jpg 380w\" ><\/figure>\n\n\n\n<h3 id=\"implementation-of-dp-approach\">Implementation of DP Approach<\/h3>\n\n\n\n<h4 id=\"c-implementation-dynamic-programming\">C++ Implementation: Dynamic Programming<\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: 700px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/657d7e6ef9438b09a8a0 title='Interviewbit Ide snippet\/657d7e6ef9438b09a8a0' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-scripts allow-same-origin allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h4 id=\"-java-implementation-dynamic-programming\"><span id=\"java-implementation-dynamic-programming\"><meta charset=\"utf-8\">Java Implementation: Dynamic Programming<\/span><\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/148ae39c39ba1ea23820 title='Interviewbit Ide snippet\/148ae39c39ba1ea23820' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h4 id=\"python-implementation-dynamic-programming\">Python Implementation: Dynamic Programming<\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: 700px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/977c2527b97e3eed0226 title='Interviewbit Ide snippet\/977c2527b97e3eed0226' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-scripts allow-same-origin allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<p><strong>Time complexity:<\/strong> O(N^2), Where N is the size of the string<br><strong>Space complexity:<\/strong> O(N^2)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"expand-around-center-approach\">Expand Around Center Approach<\/h2>\n\n\n\n<p>In fact, we could solve it in O(n^2) without using any additional array and the time remains the same.<\/p>\n\n\n\n<p>We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n &#8211; 1 such center.<\/p>\n\n\n\n<h3 id=\"dry-run-of-approach\">Dry Run of Approach<\/h3>\n\n\n\n<p><strong>Step 1<\/strong><\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Dry Run 1\"  class=\"wp-image-2306 pk-lazyload\"  width=\"704\"  height=\"280\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 704px) 100vw, 704px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-4.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-4.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-4-300x120.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-4-768x306.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-4-380x151.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-4-550x219.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-4-800x319.jpg 800w\" ><\/figure><\/div>\n\n\n\n<p>From the above image, we can see that the palindromic substring found is &#8216;bbb&#8217; with length 3.<\/p>\n\n\n\n<p><strong>Step 2<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"408\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Dry Run 2\"  class=\"wp-image-2309 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-5-1.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-5-1.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-5-1-300x120.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-5-1-768x306.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-5-1-380x151.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-5-1-550x219.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-5-1-800x319.jpg 800w\" ><\/figure>\n\n\n\n<p>From the above image, we can see that the palindromic substring found is &#8216;bbbbb&#8217; with a length of 5<\/p>\n\n\n\n<p><strong>Step-3<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"408\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Dry Run 3\"  class=\"wp-image-2312 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-8.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-8.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-8-300x120.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-8-768x306.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-8-380x151.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-8-550x219.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-8-800x319.jpg 800w\" ><\/figure>\n\n\n\n<p>From the above image, we can see that the palindromic substring found is &#8216;bbb&#8217; with length 3.<\/p>\n\n\n\n<p><strong>Last Step<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"408\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Dry Run Last Step\"  class=\"wp-image-2310 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-6-1.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-6-1.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-6-1-300x120.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-6-1-768x306.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-6-1-380x151.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-6-1-550x219.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-6-1-800x319.jpg 800w\" ><\/figure>\n\n\n\n<p>From the above image, we can see that the palindromic substring found is &#8216;bbb&#8217; with length 3.<\/p>\n\n\n\n<h3 id=\"implementation-of-above-approach\">Implementation Of Above Approach<\/h3>\n\n\n\n<h4 id=\"c-implementation-of-expand-around-center-approach\">C++ Implementation of Expand Around Center Approach<\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/c6fcaca1c8158a133260 title='Interviewbit Ide snippet\/c6fcaca1c8158a133260' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h4 id=\"java-implementation-of-expand-around-center-approach\">Java Implementation of Expand Around Center Approach<\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/43bd78d66518cffc0de9 title='Interviewbit Ide snippet\/43bd78d66518cffc0de9' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h4 id=\"-python-implementation-of-expand-around-center-approach\"><span id=\"python-implementation-of-expand-around-center-approach\"><meta charset=\"utf-8\">Python Implementation of Expand Around Center Approach<\/span><\/h4>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/fde2223699dceb896ec7 title='Interviewbit Ide snippet\/fde2223699dceb896ec7' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N^2)<br><strong>Space Complexity:<\/strong> O(1)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions<\/h2>\n\n\n\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/longest-palindromic-substring\/\" target=\"_blank\">Longest Palindromic Substring<\/a><br><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/minimum-characters-required-to-make-a-string-palindromic\/\" target=\"_blank\">Minimum Characters Required To Make String Palindromic<\/a><br><a href=\"https:\/\/www.interviewbit.com\/courses\/programming\/dynamic-programming\/\" target=\"_blank\" rel=\"noreferrer noopener\">Dynamic Programming<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<p><strong>What is the longest palindrome sentence?<\/strong><br>The largest known palindromic word is saippuakivikauppias (19 letters), which is Finnish for a dealer in lye (caustic soda).<\/p>\n\n\n\n<p><strong>What is the difference between substring and subsequence?<\/strong><br>Substring: It is a prefix or suffix of a string.<br>Subsequence: It is a subset of the string\u2019s character having the same sequential ordering as the original string.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a string, we have to find the longest palindromic substring(substring is a sequence of characters&hellip;\n","protected":false},"author":5,"featured_media":2304,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[399,398],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2301"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2301"}],"version-history":[{"count":9,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2301\/revisions"}],"predecessor-version":[{"id":10504,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2301\/revisions\/10504"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2304"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2301"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2301"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2301"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}