[Geeks for Geeks] Longest Palindrome in a String

Longest Palindrome in a String

Given a string S, find the longest palindromic substring in S. Substring of string S: S[ i . . . . j ] where 0 ≤ i ≤ j < len(S). Palindrome string: A string which reads the same backwards. More formally, S is palindrome if reverse(S) = S. Incase of conflict, return the substring which occurs first ( with the least starting index).

  • Time : O(n)
  • Space : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
string longestPalin(string S) {
if(S.empty()) return "";
string s = "#";
for(auto& ch : S) {
s.push_back(ch);
s.push_back('#');
}
int n = s.length(), len = -1, pos = -1;
int l = 0, r = -1;
vector<int> dp(n);
for(int i = 0; i < n; i++) {
dp[i] = max(0, min(r - i, (r + l - i >= 0 ? dp[r + l - i] : - 1)));
while(i + dp[i] < n and i - dp[i] >= 0 and s[i + dp[i]] == s[i - dp[i]])
dp[i]++;
if(i + dp[i] > r) {
r = i + dp[i];
l = i - dp[i];
}
if(len < (dp[i] - 1) * 2 + 1) {
pos = i - dp[i] + 1;
len = (dp[i] - 1) * 2 + 1;
}
}

string res = "";
for(int i = pos; i < pos + len; i++) {
if(s[i] == '#') continue;
res.push_back(s[i]);
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/22/PS/GeeksforGeeks/longest-palindrome-in-a-string/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.