Longest Palindrome in String Editorial

Practice Problem Link: Longest Palindrome in String | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a string s, find the longest palindrome substring in s. If there are multiple valid substrings, find the first one.

Naive Approach

The simple solution is to check each substring whether it is palindrome or not and find the longest palindrome among them.

To do that, run two nested loop to decide the start and end of each loop. Now run a third nested loop from start to end to check whether the string is palindrome or not.

If the string is a palindrome, store the starting index and string length for the longest palindrome among them.

Analysis

• Time Complexity: O(n³)
• Auxiliary Space Complexity: O(1)

Implementation

C++

string getLongestPalindrome(string s) {
   int n = s.size();
   int index  = -1, palindromeLength = 0;
   for (int i = 0; i < n; i++) {
       for (int j = i; j < n; j++) {
           int isPalindrome = 1;
           for (int k = i; k <= j; k++) {
               if (s[k] != s[j - (k - i)]) {
                   isPalindrome = 0;
               }
           }
           if (isPalindrome == 1 && j - i + 1 > palindromeLength) {
               index = i;
               palindromeLength = j - i + 1;
           }
       }
   }
   string ans = "";
   for (int i = index; i < index + palindromeLength; i++) {
       ans += s[i];
   }
   return ans;
}

Java

class Solution {
   String getLongestPalindrome(String s) {
       int n = s.length();
       int index  = -1, palindromeLength = 0;
       for (int i = 0; i < n; i++) {
           for (int j = i; j < n; j++) {
               int isPalindrome = 1;
               for (int k = i; k <= j; k++) {
                   if (s.charAt(k) != s.charAt(j - (k - i))) {
                       isPalindrome = 0;
                   }
               }
               if (isPalindrome == 1 && j - i + 1 > palindromeLength) {
                   index = i;
                   palindromeLength = j - i + 1;
               }
           }
       }
       String ans = "";
       for (int i = index; i < index + palindromeLength; i++) {
           ans += s.charAt(i);
       }
       return ans;
   }
}

Optimal Approach

The optimal approach for this problem is quite similar to the naive approach. Here instead of deciding the start index will decide the middle index for a palindromic string.

• Traverse the string and consider each index as the middle point of the palindromic string. Here two different cases will be encountered.
• Case 1: Palindromic string has even length
  • In this case, assign two pointers left = i - 1 and right  = i as centre and expand left and right in both directions while s[left] == s[right]. Keep updating the starting index and the maximum length of the palindromic string.
• Case 2: Palindromic string has odd length
  • In this case, the two pointers will be assigned as left = i -1 nd right = i + 1 as index i is the middle element. Now repeat the same process as of the even length string.
• Return the palindromic substring having the maximum length.

Analysis

• Time Complexity: O(n²)
• Auxiliary Space Complexity: O(1)

Implementation

C++

string getLongestPalindrome(string s) {
   int n = s.size();
   int index  = 0, palindromeLength = 1;
   for (int i = 1; i < n; i++) {
       int left = i - 1, right = i;
       while(left >= 0 && right < n && s[left] == s[right]) {
           if(right - left + 1 > palindromeLength) {
               index = left;
               palindromeLength = right - left + 1;
           }
           left--;
           right++;
       }
       left = i - 1;
       right = i + 1;
       while(left >= 0 && right < n && s[left] == s[right]) {
           if(right - left + 1 > palindromeLength) {
               index = left;
               palindromeLength = right - left + 1;
           }
           left--;
           right++;
       }
   }
   string ans = "";
   for (int i = index; i < index + palindromeLength; i++) {
       ans += s[i];
   }
   return ans;
}

Java

class Solution {
   String getLongestPalindrome(String s) {
       int n = s.length();
       int index  = 0, palindromeLength = 1;
       for (int i = 1; i < n; i++) {
           int left = i - 1, right = i;
           while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
               if(right - left + 1 > palindromeLength) {
                   index = left;
                   palindromeLength = right - left + 1;
               }
               left--;
               right++;
           }
           left = i - 1;
           right = i + 1;
           while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
               if(right - left + 1 > palindromeLength) {
                   index = left;
                   palindromeLength = right - left + 1;
               }
               left--;
               right++;
           }
           
       }
       String ans = "";
       for (int i = index; i < index + palindromeLength; i++) {
           ans += s.charAt(i);
       }
       return ans;
   }
}