[LeetCode Road] Longest Palindromic Substring - Solution/C++

5. Longest Palindromic Substring

Question:

Given a string s, return the longest palindromic substring in s.

Example:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: s = "cbbd"
Output: "bb"

Input: s = "a"
Output: "a"

Input: s = "ac"
Output: "a"

Constraints:

1 <= s.length <= 1000

s consist of only digits and English letters (lower-case and/or upper-case)

Source code

Version 1

Idea:

There are two situations of the palindromic that are shown as below:

Therefore, you should calculate the maximum length of the valid string for two situation at 11 line.

Let's look at getLen() function. you need to delcare two variables, l is represented the left index and r is represented the right index, use two indexes as the margins of string to find the longest substring. If l is smaller than 0 or r is equal to n or a character of s[l] and s[r] are not the same, the while loop will be stop, and return r - l - 1 length.

Why is r - l - 1? Because the value of r and l are added 1 when break the while loop, as below:

Hence, must be additionally substract 1.

After getting the result from getLen(), if the result is bigger than len at 13 line, store the result and calculate the start index of the substring by using the i and len.

Finally, you can use substr() to return the exact substring!

Time complexity: O(n²)
Space complexity: O(1)

class Solution {
public:
    string longestPalindrome(string s) {
        const int n = s.length();
        if(n <= 1) return s;
        
        int len = 0;
        int startIndex = 0;
        
        for(int i = 0; i < n; i++){
            int validLen = max(getLen(i, i, n, s), getLen(i, i+1, n, s));
            
            if(validLen > len){
                len = validLen;
                startIndex = i - (len - 1) / 2;
            }
        }
        return s.substr(startIndex, len);
    }
private:
    int getLen(int l, int r, int n, string s){
        while(l >= 0 && r < n && s[l]==s[r]){
            l--;
            r++;
        }
        return r - l - 1;
    }
};