5. Longest palindrome substring

5_solution1_dp.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

char *longestPalindrome(char *s) {
  int n = strlen(s);
  bool *dp = calloc(n * n, sizeof(bool)); // dp[i * n + j]: s[i..j] is a palindrome
  int bestStart = 0, bestLen = 1;

  // Every single character is a palindrome
  for (int i = 0; i < n; i++)
    dp[i * n + i] = true;

  // Fill by increasing substring length
  for (int len = 2; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
      int j = i + len - 1;

      if (s[i] == s[j] && (len == 2 || dp[(i + 1) * n + (j - 1)])) {
        dp[i * n + j] = true;
        if (len > bestLen) {
          bestStart = i;
          bestLen = len;
        }
      }
    }
  }
  free(dp);

  char *res = malloc(bestLen + 1);
  memcpy(res, s + bestStart, bestLen);
  res[bestLen] = '\0';
  return res;
}

5_solution2_no_dp.c

#include <stdlib.h>
#include <string.h>

// Grow outward from the center (left, right) while the ends match.
// Returns the length of the palindrome found.
static int expand(const char *s, int n, int left, int right) {
  while (left >= 0 && right < n && s[left] == s[right]) {
    left--;
    right++;
  }
  return right - left - 1;
}

char *longestPalindrome(char *s) {
  int n = strlen(s);
  int bestStart = 0, bestLen = 0;

  for (int i = 0; i < n; i++) {
    int oddLen = expand(s, n, i, i);      // center on a character: "aba"
    int evenLen = expand(s, n, i, i + 1); // center between two characters: "abba"
    int len = oddLen > evenLen ? oddLen : evenLen;

    if (len > bestLen) {
      bestLen = len;
      bestStart = i - (len - 1) / 2;
    }
  }

  char *res = malloc(bestLen + 1);
  memcpy(res, s + bestStart, bestLen);
  res[bestLen] = '\0';
  return res;
}

5_solution1_dp.cpp

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int bestStart = 0, bestLen = 1;

    // Every single character is a palindrome
    for (int i = 0; i < n; i++)
      dp[i][i] = true;

    // Fill by increasing substring length
    for (int len = 2; len <= n; len++) {
      for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;

        if (s[i] == s[j] && (len == 2 || dp[i + 1][j - 1])) {
          dp[i][j] = true;
          if (len > bestLen) {
            bestStart = i;
            bestLen = len;
          }
        }
      }
    }
    return s.substr(bestStart, bestLen);
  }
};

5_solution2_no_dp.cpp

#include <algorithm>
#include <string>

using namespace std;

class Solution {
  // Grow outward from the center (left, right) while the ends match.
  // Returns the length of the palindrome found.
  int expand(const string &s, int left, int right) {
    while (left >= 0 && right < (int)s.size() && s[left] == s[right]) {
      left--;
      right++;
    }
    return right - left - 1;
  }

public:
  string longestPalindrome(string s) {
    int bestStart = 0, bestLen = 0;

    for (int i = 0; i < (int)s.size(); i++) {
      int oddLen = expand(s, i, i); // center on a character: "aba"
      int evenLen =
          expand(s, i, i + 1); // center between two characters: "abba"
      int len = max(oddLen, evenLen);

      if (len > bestLen) {
        bestLen = len;
        bestStart = i - (len - 1) / 2;
      }
    }
    return s.substr(bestStart, bestLen);
  }
};

5_solution1_dp.go

package dp

func longestPalindrome(s string) string {
    n := len(s)
    dp := make([][]bool, n)
    for i := range dp {
        dp[i] = make([]bool, n)
    }
    bestStart, bestLen := 0, 1

    // Every single character is a palindrome
    for i := 0; i < n; i++ {
        dp[i][i] = true
    }

    // Fill by increasing substring length
    for length := 2; length <= n; length++ {
        for i := 0; i+length-1 < n; i++ {
            j := i + length - 1

            if s[i] == s[j] && (length == 2 || dp[i+1][j-1]) {
                dp[i][j] = true
                if length > bestLen {
                    bestStart, bestLen = i, length
                }
            }
        }
    }
    return s[bestStart : bestStart+bestLen]
}

5_solution2_no_dp.go

package dp

// expand grows outward from the center (left, right) while the ends match.
// Returns the length of the palindrome found.
func expand(s string, left, right int) int {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
    }
    return right - left - 1
}

func longestPalindrome(s string) string {
    bestStart, bestLen := 0, 0

    for i := range len(s) {
        oddLen := expand(s, i, i)    // center on a character: "aba"
        evenLen := expand(s, i, i+1) // center between two characters: "abba"
        length := max(oddLen, evenLen)

        if length > bestLen {
            bestLen = length
            bestStart = i - (length-1)/2
        }
    }
    return s[bestStart : bestStart+bestLen]
}

5_solution1_dp.java

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int bestStart = 0, bestLen = 1;

        // Every single character is a palindrome
        for (int i = 0; i < n; i++)
            dp[i][i] = true;

        // Fill by increasing substring length
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;

                if (s.charAt(i) == s.charAt(j) && (len == 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (len > bestLen) {
                        bestStart = i;
                        bestLen = len;
                    }
                }
            }
        }
        return s.substring(bestStart, bestStart + bestLen);
    }
}

5_solution2_no_dp.java

class Solution {
    // Grow outward from the center (left, right) while the ends match.
    // Returns the length of the palindrome found.
    private int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    public String longestPalindrome(String s) {
        int bestStart = 0, bestLen = 0;

        for (int i = 0; i < s.length(); i++) {
            int oddLen = expand(s, i, i); // center on a character: "aba"
            int evenLen = expand(s, i, i + 1); // center between two characters: "abba"
            int len = Math.max(oddLen, evenLen);

            if (len > bestLen) {
                bestLen = len;
                bestStart = i - (len - 1) / 2;
            }
        }
        return s.substring(bestStart, bestStart + bestLen);
    }
}

5_solution1_dp.js

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(false));
  let bestStart = 0, bestLen = 1;

  // Every single character is a palindrome
  for (let i = 0; i < n; i++) dp[i][i] = true;

  // Fill by increasing substring length
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;

      if (s[i] === s[j] && (len === 2 || dp[i + 1][j - 1])) {
        dp[i][j] = true;
        if (len > bestLen) {
          bestStart = i;
          bestLen = len;
        }
      }
    }
  }
  return s.substring(bestStart, bestStart + bestLen);
};

5_solution2_no_dp.js

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  // Grow outward from the center (left, right) while the ends match.
  // Returns the length of the palindrome found.
  const expand = (left, right) => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return right - left - 1;
  };

  let bestStart = 0, bestLen = 0;

  for (let i = 0; i < s.length; i++) {
    const oddLen = expand(i, i); // center on a character: "aba"
    const evenLen = expand(i, i + 1); // center between two characters: "abba"
    const len = Math.max(oddLen, evenLen);

    if (len > bestLen) {
      bestLen = len;
      bestStart = i - Math.floor((len - 1) / 2);
    }
  }
  return s.substring(bestStart, bestStart + bestLen);
};

5_solution1_dp.py

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        best_start, best_len = 0, 1

        # Every single character is a palindrome
        for i in range(n):
            dp[i][i] = True

        # Fill by increasing substring length
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1

                if s[i] == s[j] and (length == 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    if length > best_len:
                        best_start, best_len = i, length

        return s[best_start : best_start + best_len]

5_solution2_no_dp.py

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left: int, right: int) -> int:
            """Grow outward from the center (left, right) while the ends match.
            Returns the length of the palindrome found."""
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return right - left - 1

        best_start, best_len = 0, 0

        for i in range(len(s)):
            odd_len = expand(i, i)  # center on a character: "aba"
            even_len = expand(i, i + 1)  # center between two characters: "abba"
            length = max(odd_len, even_len)

            if length > best_len:
                best_len = length
                best_start = i - (length - 1) // 2

        return s[best_start : best_start + best_len]

5_solution1_dp.rs

impl Solution {
    pub fn longest_palindrome(s: String) -> String {
        let b = s.as_bytes();
        let n = b.len();
        let mut dp = vec![vec![false; n]; n];
        let (mut best_start, mut best_len) = (0, 1);

        // Every single character is a palindrome
        for i in 0..n {
            dp[i][i] = true;
        }

        // Fill by increasing substring length
        for len in 2..=n {
            for i in 0..=n - len {
                let j = i + len - 1;

                if b[i] == b[j] && (len == 2 || dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    if len > best_len {
                        best_start = i;
                        best_len = len;
                    }
                }
            }
        }
        s[best_start..best_start + best_len].to_string()
    }
}

5_solution2_no_dp.rs

impl Solution {
    pub fn longest_palindrome(s: String) -> String {
        let b = s.as_bytes();
        let (mut best_start, mut best_len) = (0, 0);

        for i in 0..b.len() {
            let odd_len = Self::expand(b, i as i32, i as i32); // center on a character: "aba"
            let even_len = Self::expand(b, i as i32, i as i32 + 1); // center between two characters: "abba"
            let len = odd_len.max(even_len);

            if len > best_len {
                best_len = len;
                best_start = i - (len - 1) / 2;
            }
        }
        s[best_start..best_start + best_len].to_string()
    }

    // Grow outward from the center (left, right) while the ends match.
    // Returns the length of the palindrome found.
    // left is i32 so it can step below 0 without underflow
    fn expand(b: &[u8], mut left: i32, mut right: i32) -> usize {
        while left >= 0 && (right as usize) < b.len() && b[left as usize] == b[right as usize] {
            left -= 1;
            right += 1;
        }
        (right - left - 1) as usize
    }
}