Jan 19 - Daily Programming Diary

Copylongest-palindromic-substring.cpp: copy code to clipboard
1string longestPalindrome(string s) {
2    if (s.length() < 2)
3        return s;
4    int max_len = 0;
5    int start_idx = 0;
6    int i = 0;
7    while (i < s.length()) {
8        int right = i;
9        int left = i;
10        //find the middle of a palindrome
11        while (right < s.length() - 1 && s[right] == s[right + 1]) {
12            right++; 
13        }
14        i = right + 1;
15        //expand from the middle out
16        while (right < s.length() - 1 && left > 0 && s[right + 1] == s[left - 1]) {
17            right++;
18            left--;
19        }
20        int new_len = right - left + 1;
21        if (new_len > max_len) {
22            start_idx = left;
23            max_len = new_len;
24        }
25    }
26    return s.substr(start_idx, max_len);
27}