lp.cc

static bool cache[1024][1024];

class Solution {
public:
  std::string longestPalindrome(std::string s) {
    int sz = (int)s.size();
    if (sz == 0) return s;
    int start = 0, len = 1;
    
    memset(cache, 0, sizeof(cache));

    for (auto i = 0; i < sz; i++) {
      cache[i][i] = 1;
    }
    
    for (auto i = 0; i < sz - 1; i++) {
      auto j = 1 + i;
      if (s[i] == s[j]) {
	cache[i][j] = 1;

	start = i;
	len = 2;
      }
    }

    for (auto k = 2; k < sz; k++) {
      for (auto i = 0; i < sz - k; i++) {
	auto j = i + k;
	auto p = cache[i+1][j-1];

	if (p) {
	  if (s[i] == s[j]) {
	    cache[i][j] = 1;

	    if (j-i+1 > len) {
	      start = i;
	      len = (j-i+1);
	    }
	  }
	}
      }
    }

    return s.substr(start, len);
  }
};