Longest Palindromic Substring

• Time : O(n)
• Space : O(n)

using namespace std;

string longestPalindromicSubstring(string str) {
	string s = "#";
	for(auto& ch : str) {
		s.push_back(ch);
		s.push_back('#');
	}
	vector<int> dp(s.length());
	int l = 0, r = -1;
	for(int i = 0; i < s.length(); i++) {
		dp[i] = min(0,max(r - i, (l + r - i >= 0 ? dp[l + r - i] : -1)));
		while(i - dp[i] >= 0 and s[i + dp[i]] == s[i - dp[i]])
			dp[i]++;
		
		if(r < i + dp[i]) {
			r = i + dp[i];
			l = i - dp[i];
		}
	}
		
		int ma = -1, idx = -1;
		for(int i = 0; i < dp.size(); i++) {
			if(dp[i] > ma) {
				ma = dp[i];
				idx = i;
			}
		}
		string res = "";
		for(int i = idx - ma + 1; i < idx + ma; i++) {
			if(s[i] == '#') continue;
			res.push_back(s[i]);
		}
	
  return res;
}