source: https://leetcode.com/problems/longest-palindromic-substring/
C/C++ Solution to LeetCode problem 5. Longest Palindromic Substring.
Problem
Given a string s
, return the longest palindromic substring in s
.
Examples
Example 1:
Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.
Example 2:
Input: s = “cbbd”
Output: “bb”
Constraints
1 <= s.length <= 1000
s
consist of only digits and English letters.
Solution
We will use two pointers.
- We will iterate through every character.
- For each character, one pointer will be to the left and the other to the right.
- Using the character as the center: As long as the character at the pointers position are equal, we calculate the size and update the longest palindomic string found to this point, and we “expand” the pointers (move one place to the left and right)
- For palindromic string of even size, we start with the pointers one next to the other, and we do the same process of comparing and expanding.
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 longestPalindrome(string s) {
string result = ""s + s[0];
int l = 0;
int r = 0;
int m = 1;
for (int i=1; i<s.size(); i+=1) {
l = i-1;
r = i+1;
while (l>=0 && r<s.size() && s[l] == s[r]) {
if ((r-l) + 1 > m) {
m = (r-l) + 1;
result = s.substr(l, m);
}
l--;
r++;
}
l = i-1;
r = i;
while (l>=0 && r<s.size() && s[l] == s[r]) {
if ((r-l) + 1 > m) {
m = (r-l) + 1;
result = s.substr(l, m);
}
l--;
r++;
}
}
return result;
}
};