5. Longest Palindromic Substring

Description:

Solution:

Brute Force --> time complexity will be O(n^3). However, it takes a lot of time.

 

Instead of Brute Force, we are gonna set left & right pointer for the string.

In the for loop, we are gonna check if the string is odd number length or not. 

We keep update the resLen, and make sure it should be bigger than previous resLen.

 

In odd number case, l & r starts from s[0]. We keep moving those pointers to move until l & r is the middle of the longest palindromic substring.

In even number case, we guess the substring will be the even number. r is right next value of l. 

 

# Note: The odd number and even number case refers the substring, not a given s. Also, we first check the odd case and then even case!!

 

 

Time Complexity: O(n^2)