[Leetcode] Longest Palindromic Substring

Given a string s, return the longest

in s.

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.

How to understand?

This problem is checking the longest palindrome of sub string in input string. Palindrome has symmetrical characters in the string. ex) aba, level, oxo

How to approach?

Brute force

function longestPalindrome(s: string): string {
    function check(i, j) {
        let left = i;
        let right = j - 1
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++
            right--
        }
        return true;
    }

    for (let length = s.length; length > 0; length--) {
        for (let start = 0; start <= s.length - length; start++) {
            if (check(start, start + length)) {
                return s.slice(start, start + length)
            }
        }
    }

    return ''
};

create double for loop to check the length and the start point in the string. its purpose is checking all the valid sub array from the longest one.
outer for loop is checking length of sub array, and inner for loop checks the start point, if condition will use check function, if it is true then return the sliced string.
otherwise, return empty array since there is no palindrome in this s string.
function check will get the start point and start point + length as inputs.
set left and right pointer, which is i, and j -1, since -1 to exclude the length itself.
and create the while loop to check if the left pointer is smaller than right pointer. and if condition to check left pointer string character and right pointer string character is not same then return false since it is not palindrome.
and move left pointer to the right, right pointer to the left.
if it's not early returned false, then it means all the characters from the pointers are same so it's palindrome. return true.

summary

you can see it's using double for loop + check function to get the n character to check. so T c is n³, S c is O 1 when it's the worst case to check all of them without early return.

Expand

function longestPalindrome(s: string): string {
    function expand(i, j) {
        let left = i;
        let right = j;

        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--
            right++
        }

        return s.slice(left + 1, right)
    }

    let ans = ""
    for (let i = 0; i < s.length; i++) {
        let odd = expand(i, i)
        if (odd.length > ans.length) {
            ans = odd
        }

        let even = expand(i, i + 1)
        if (even.length > ans.length) {
            ans = even
        }
    }

    return ans;
};

think of this problem checking all the centre point of the substrings.
then possible centre point will be 2n-1, when it has n char in the input string.
n possible centre point in odd length substring, n-1 possible centre in even length substring.
create empty string to return it at the end.
create for loop to check all the char in input string.
create odd case and even case.
when the returned string's length is longer than the existing answer's length then replace it.
odd case will check the i,i centre and even case will check i,i+1 case.
the expand function declared above will expand one by one from the centre in odd/even cases.
how? set left and right pointer as the input source. and create while loop to check if the left and right pointer exceeds 0 or the input string length, if it doesn't then check if left index element and right index element in input string and if it's same then to check the next chars in input string by incrementing right pointer and decrementing left pointer by one.
while loop breaks, that means the left, right pointer element in input string is not same, so slice the input string by left+1,right index. because it shouldn't include the index pointer which didn't meet the while loop condition.
lastly when there is the longest palindrome substring, return the ans.

summary

this technique use two pointers in expand function and check from centre to outside. its T C is O n², and S C is O 1.