5. Longest Palindromic Substring 🔥

Medium

Problem:

Find the longest palindromic substring.

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

https://leetcode.com/problems/group-anagrams/

What to learn:

Two Pointers

It primarily targets sorted arrays, and solves problems by freely moving two pointers from left to right.

Sliding Window

It can also be applied to unsorted arrays. The window size is fixed and only moves in the left or right direction.

Name	Sorted	Window size	Move
Two pointers	Most O	Variable	Bidirectional left-right
Sliding window	X	Fixed	Unidirectional left or right

Solutions:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = ""
        for left in range(len(s)):
            for right in range(len(s) - 1, left, -1):
                if s[left] == s[right]:
                    temp = s[left:right + 1]
                    if temp == temp[::-1] and len(temp) > len(longest):
                        longest = temp
                        break
        return longest if longest else s[0]

Another approach: a solution that expands from the center

1. Two-pointers, consisting of 2 spaces(even-length palindrome) and 3 spaces(odd-length palindrome), move from the beginning to the end of the string like a sliding window.

2. When the string that comes into the window is a palindrome, it stops at that spot and extends the two pointers.

3. Handle the exception.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # Expand around the center of a potential palindrome
        def expand(left: int, right: int) -> str:
            while left >= 0 and right <= len(s) and s[left] == s[right - 1]:
                left -= 1
                right += 1
            return s[left + 1 : right - 1]
        
        # Exception handling
        # the string s has one or zero characters or it is itself a palindrome
        if len(s) < 2 or s == s[::-1]:
            return s
        
        # Move sliding window to the right
        result = ''
        for i in range(len(s) - 1):
            result = max(result, expand(i, i + 1), expand(i, i + 2), key=len)
        return result

Nested Function

It's not often used from work, but it's a very frequently used feature in coding tests where solutions often need to be achieved with a single function.

• It can freely read the local variables of the parent function, so there's no need to pass parameters each time.

• If it's a mutable object, it can be manipulated by various operations. Immutable objects like strings cannot be manipulated.

• If reassignment occurs, the reference ID changes and it is declared as a separate local variable. In other words, the reassigned value (modified value) is not reflected in the parent function.

Operator manipulation

def parent_function(a: List[int]):
    b: List[int] = a
    print(id(b), b)
    
    def nested_function1():
        b.append(4)
        print(id(b), b)
        
    def nested_function2():
        print(id(b), b)
    
    nested_function1()
    nested_function2()
    
parent_function([1,2,3])

Reassignment

def parent_function(t: str):
    text: str = t
    print(id(text), text)
    
    def nested_function1():
        text = 'Hello!'
        print(id(text), text)
    def nested_function2():
        print(id(text), text)
    
    nested_function1()
    nested_function2()
    
parent_function('Hello')