-
Notifications
You must be signed in to change notification settings - Fork 0
/
33_longest-palindromic-substring.cpp
52 lines (44 loc) · 1.3 KB
/
33_longest-palindromic-substring.cpp
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// DATE: 05-Aug-2023
/* PROGRAM: 33_String - Longest Palindromic Substring
https://leetcode.com/problems/longest-palindromic-substring/
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
*/
// @ankitsamaddar @Aug_2023
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
string longestPalindrome(string s) {
string res;
for (int i = 0; i < s.length(); i++) {
string s1 = palindrome(s, i, i); // odd length sub-string
string s2 = palindrome(s, i, i + 1); // even length sub-string
// check till last element if even length
// sub-string
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
string palindrome(string s, int l, int r) {
while (l >= 0 && r < s.length() && s[l] == s[r]) {
l--;
r++;
}
return s.substr(l + 1, r - l - 1);
}
};
int main() {
string s = "babad";
Solution sol;
cout << sol.longestPalindrome(s);
return 0;
}