Longest Palindromic Substring

The problem of finding the Longest Palindromic Substring is a classic and fundamental challenge in computer science and string manipulation. A palindrome is a sequence of characters that reads the same forwards as it does backward. In this problem, the task is to identify and extract the longest substring within a given input string that forms a palindrome.

Several common methods and algorithms exist to solve this problem, each with its own trade-offs in terms of time and space complexity. Here is a brief introduction to some of the common methods:

• Brute Force: The simplest approach involves checking all possible substrings in the input string to see if they are palindromes. While conceptually straightforward, this method has a time complexity of O(n^3) and is not practical for large input strings.
• Expand Around Center: The approach treats each character in the input string as a potential center of a palindrome and expands outward to find the longest palindrome. It has a time complexity of O(n^2) and is often faster in practice due to small constant factors.
• Dynamic Programming: This approach utilizes a dynamic programming table to store information about whether substrings are palindromes or not. It has a time complexity of O(n^2) and is more efficient than brute force.
• Manacher’s Algorithm: This is an advanced and highly efficient algorithm that can find the longest palindromic substring in linear time, O(n). It employs clever techniques to avoid redundant character comparisons.
• Suffix Tree: Constructing the suffix tree takes O(n^2) time, but once built, it can answer palindrome-related queries efficiently.
• Palindrome Tree: A specialized data structure known as a palindrome tree is designed for solving palindrome-related problems efficiently. It can find the longest palindromic substring in linear time.

During coding interview, it’s generally not recommended to start with the brute force solution. Dynamic programming is a good choice for an interview because it’s a well-known technique with a reasonable time complexity O(n^2). Expand around center is also a good choice for a coding interview because it’s relatively easy to implement.

While highly efficient, Manacher’s algorithm, Suffix Tree or Palindrome Tree are typically not suitable for a coding interview unless the interviewer explicitly asks for them. They are complex to implement and may not be expected in most interview scenarios.

Expand Around Center

The idea behind this approach is to consider each character in the given string as a potential center of a palindrome and then expand outward to check if the characters on both sides form a valid palindrome.

This technique is effective for solving problems where you need to find palindromes because it takes advantage of the inherent symmetry of palindromes.

#include <cassert>
#include <iostream>
#include <string>
using namespace std;

string expandAroundCenter(string s, int left, int right) {
  while (left >= 0 && right < s.length() && s[left] == s[right]) {
    left--;
    right++;
  }
  return s.substr(left + 1, right - left - 1);
}

string longestPalindrome(string s) {
  if (s.empty())
    return "";

  string longest = "";
  for (int i = 0; i < s.length(); i++) {
    string oddPalindrome = expandAroundCenter(s, i, i);
    string evenPalindrome = expandAroundCenter(s, i, i + 1);

    if (oddPalindrome.length() > longest.length()) {
      longest = oddPalindrome;
    }
    if (evenPalindrome.length() > longest.length()) {
      longest = evenPalindrome;
    }
  }

  return longest;
}

int main() {
  assert(longestPalindrome("a") == "a");
  assert(longestPalindrome("cbbd") == "bb");
  cout << "All tests passed!" << endl;
  return 0;
}

This algorithm has a time complexity of O(n^2) because for each character in the string, it potentially expands outward to both the left and right sides. Space complexity is O(1) as it only requires a few extra variables to keep track of the longest palindrome found so far and the current positions of the pointers as it iterates through the input string.

Dynamic Programming

The dynamic programming approach for finding the longest palindromic substring involves using a table to store whether substrings are palindromes or not. This approach has a time complexity of O(n^2), where n is the length of the input string.

#include <iostream>
#include <string>
#include <vector>
#include <cassert>
using namespace std;

string longestPalindrome(string s) {
  if (s.empty())
    return "";

  int n = s.length();
  vector<vector<bool>> dp(n, vector<bool>(n, false));
  int start = 0;         // Start index of the longest palindromic substring
  int max_length = 1;    // Length of the longest palindromic substring

  // All substrings of length 1 are palindromes
  for (int i = 0; i < n; i++) {
    dp[i][i] = true;
  }

  // Check for palindromes of length 2
  for (int i = 0; i < n - 1; i++) {
    if (s[i] == s[i + 1]) {
      dp[i][i + 1] = true;
      start = i;
      max_length = 2;
    }
  }

  // Check for palindromes of length 3 or more
  for (int len = 3; len <= n; len++) {
    for (int i = 0; i < n - len + 1; i++) {
      int j = i + len - 1; // Ending index of the current substring

      // Check if the current substring is a palindrome
      if (s[i] == s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;

        // Update the longest palindrome information if needed
        if (len > max_length) {
          start = i;
          max_length = len;
        }
      }
    }
  }

  // Extract and return the longest palindromic substring
  return s.substr(start, max_length);
}

int main() {
  assert(longestPalindrome("a") == "a");
  assert(longestPalindrome("cbbd") == "bb");
  cout << "All tests passed!" << endl;
  return 0;
}