Problem

Imagine you’re working with DNA sequences to uncover regions critical for enzyme binding and gene regulation. Your task is to develop an algorithm that, given a DNA strand represented as a string (e.g., “AGCTTTCGA”), locates and returns the longest contiguous palindromic segment. Identifying this region is key because palindromic sequences in DNA often serve as specific recognition sites for enzymes and play a role in forming secondary structures that influence biological functions.

Example 1:

Input: s = “ATGCATG”
Output: “ATGCA”
Explanation: “ATGCA” is the longest palindromic substring in the given DNA sequence.

Example 2:

Input: s = “AGTCTGGA”
Output: “TCT”
Explanation: “TCT” is the longest palindromic substring in the given DNA sequence.

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

Java Solution

class Solution {
  public String longestPalindrome(String s) {
    if (s.isEmpty())
      return "";

    // (start, end) indices of the longest palindrome in s
    int[] indices = {0, 0};

    for (int i = 0; i < s.length(); ++i) {
      int[] indices1 = extend(s, i, i);
      if (indices1[1] - indices1[0] > indices[1] - indices[0])
        indices = indices1;
      if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
        int[] indices2 = extend(s, i, i + 1);
        if (indices2[1] - indices2[0] > indices[1] - indices[0])
          indices = indices2;
      }
    }

    return s.substring(indices[0], indices[1] + 1);
  }

  // Returns the (start, end) indices of the longest palindrome extended from
  // the substring s[i..j].
  private int[] extend(final String s, int i, int j) {
    for (; i >= 0 && j < s.length(); --i, ++j)
      if (s.charAt(i) != s.charAt(j))
        break;
    return new int[] {i + 1, j - 1};
  }
}

Initialize start and maxLength for result substring.
Iterate through the given string s using the index i.
For each index i, create two pointers l and r starting at i.
Check if there’s a consecutive sequence of identical characters, increment the right pointer r until the end of the sequence is reached.
Update the index i to the current value of r.
Expand the pointers l and r outwards to find the longest palindromic substring, checking that characters on both sides are equal.
If the current length of the substring is greater than maxLength, update start and maxLength.
Return the longest palindromic substring using the start and maxLength.

C++ Solution

class Solution {
 public:
  string longestPalindrome(string s) {
    if (s.empty())
      return "";

    // (start, end) indices of the longest palindrome in s
    pair<int, int> indices{0, 0};

    for (int i = 0; i < s.length(); ++i) {
      const auto [l1, r1] = extend(s, i, i);
      if (r1 - l1 > indices.second - indices.first)
        indices = {l1, r1};
      if (i + 1 < s.length() && s[i] == s[i + 1]) {
        const auto [l2, r2] = extend(s, i, i + 1);
        if (r2 - l2 > indices.second - indices.first)
          indices = {l2, r2};
      }
    }

    return s.substr(indices.first, indices.second - indices.first + 1);
  }

 private:
  // Returns the (start, end) indices of the longest palindrome extended from
  // the substring s[i..j].
  pair<int, int> extend(const string& s, int i, int j) {
    for (; i >= 0 && j < s.length(); --i, ++j)
      if (s[i] != s[j])
        break;
    return {i + 1, j - 1};
  }
};

Initialize start and maxLength for result substring.
Iterate through the given string s using the index i.
For each index i, create two pointers l and r starting at i.
Check if there’s a consecutive sequence of identical characters, increment the right pointer r until the end of the sequence is reached.
Update the index i to the current value of r.
Expand the pointers l and r outwards to find the longest palindromic substring, checking that characters on both sides are equal.
If the current length of the substring is greater than maxLength, update start and maxLength.
Return the longest palindromic substring using the start and maxLength.

Python Solution

class Solution:
  def longestPalindrome(self, s: str) -> str:
    if not s:
      return ''

    # (start, end) indices of the longest palindrome in s
    indices = [0, 0]

    def extend(s: str, i: int, j: int) -> tuple[int, int]:
      """
      Returns the (start, end) indices of the longest palindrome extended from
      the substring s[i..j].
      """
      while i >= 0 and j < len(s):
        if s[i] != s[j]:
          break
        i -= 1
        j += 1
      return i + 1, j - 1

    for i in range(len(s)):
      l1, r1 = extend(s, i, i)
      if r1 - l1 > indices[1] - indices[0]:
        indices = l1, r1
      if i + 1 < len(s) and s[i] == s[i + 1]:
        l2, r2 = extend(s, i, i + 1)
        if r2 - l2 > indices[1] - indices[0]:
          indices = l2, r2

    return s[indices[0]:indices[1] + 1]

Initialize start and maxLength for result substring.
Iterate through the given string s using the index i.
For each index i, create two pointers l and r starting at i.
Check if there’s a consecutive sequence of identical characters, increment the right pointer r until the end of the sequence is reached.
Update the index i to the current value of r.
Expand the pointers l and r outwards to find the longest palindromic substring, checking that characters on both sides are equal.
If the current length of the substring is greater than maxLength, update start and maxLength.
Return the longest palindromic substring using the start and maxLength.

JavaScript Solution

var longestPalindrome = function (s) {
    let longest = '';

    // loop through string once
    for (let i = 0; i < s.length; i++) {
        // use two different starting positions to
        // account for even or odd strings
        checkLeftAndRight(i, i);
        checkLeftAndRight(i, i + 1);
    }

    function checkLeftAndRight(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            // subtract left from right and add one to get current
            // length of substring
            if (right - left + 1 > longest.length) {
                // set longest to current substring
                longest = s.slice(left, right + 1);
            }
            left--;
            right++;
        }
    }

    return longest;
};

Initialize start and maxLength for result substring.
Iterate through the given string s using the index i.
For each index i, create two pointers l and r starting at i.
Check if there’s a consecutive sequence of identical characters, increment the right pointer r until the end of the sequence is reached.
Update the index i to the current value of r.
Expand the pointers l and r outwards to find the longest palindromic substring, checking that characters on both sides are equal.
If the current length of the substring is greater than maxLength, update start and maxLength.
Return the longest palindromic substring using the start and maxLength.

In this problem, we are asked to find the longest palindromic substring within a given string. A palindrome is a sequence that reads the same forwards as backwards, such as “racecar” or “madam”. The goal is to identify the longest sequence of characters in the input string that maintains its symmetry when read from both ends.

To put this into context, imagine you are playing a word game with friends such as otteretto where you must find words hidden within a larger phrase. Your mission is to locate and highlight the longest word that appears symmetrical on either side of a central point. This could be particularly useful for puzzle enthusiasts or language learners looking to practice their palindromic recognition skills.

In real life, this problem might arise when analyzing data streams that contain user-provided input, such as comments or feedback. By identifying the longest palindromes in the text, we can gain insights into common phrases or repeated patterns of communication within a dataset. This could be useful for improving customer experience by understanding how users express themselves effectively and efficiently.

The solution to this problem may involve algorithms like dynamic programming, which breaks down the original string into smaller substrings, checks their symmetry, and then combines the results to find the longest palindromic substring overall. By leveraging such techniques, we can identify meaningful patterns within large datasets in a computationally efficient manner, providing valuable information for further analysis or decision-making processes.

In summary, this problem demonstrates the importance of identifying symmetric sequences (palindromes) within strings and showcases how these algorithms can be applied to real-world data analysis scenarios.

Problem#

Java Solution#

C++ Solution#

Python Solution#

JavaScript Solution#

Problem

Java Solution

C++ Solution

Python Solution

JavaScript Solution