longest_palindromic_substring

View Source

 1# @leet start
 2class Solution:
 3    def longestPalindrome(self, s: str) -> str:
 4        """
 5        To find the longest palindromic substring, we want to take each
 6        character in the string and then expand it by one on each side.
 7        If both of the expanded characters are the same, we can continue
 8        expanding the palindrome indefinitely.
 9
10        To do this for odd sized palindromes, we set our left and right pointer
11        to be equal, and for even length palindromes, we set them one apart from
12        each other.
13        """
14        n = len(s)
15        res = ""
16        max_len = 0
17
18        def expand(l, r):
19            nonlocal n, res, max_len
20            while l >= 0 and r < n and s[l] == s[r]:
21                if r - l + 1 > max_len:
22                    res = s[l : r + 1]
23                    max_len = r - l + 1
24                l -= 1
25                r += 1
26
27        for i in range(n):
28            # expand from the center
29            l, r = i, i
30            expand(l, r)
31            l, r = i, i + 1
32            expand(l, r)
33
34        return res
35
36
37# @leet end
38
39
40def test():
41    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def longestPalindrome(self, s: str) -> str:
 5        """
 6        To find the longest palindromic substring, we want to take each
 7        character in the string and then expand it by one on each side.
 8        If both of the expanded characters are the same, we can continue
 9        expanding the palindrome indefinitely.
10
11        To do this for odd sized palindromes, we set our left and right pointer
12        to be equal, and for even length palindromes, we set them one apart from
13        each other.
14        """
15        n = len(s)
16        res = ""
17        max_len = 0
18
19        def expand(l, r):
20            nonlocal n, res, max_len
21            while l >= 0 and r < n and s[l] == s[r]:
22                if r - l + 1 > max_len:
23                    res = s[l : r + 1]
24                    max_len = r - l + 1
25                l -= 1
26                r += 1
27
28        for i in range(n):
29            # expand from the center
30            l, r = i, i
31            expand(l, r)
32            l, r = i, i + 1
33            expand(l, r)
34
35        return res

def longestPalindrome(self, s: str) -> str: View Source

 4    def longestPalindrome(self, s: str) -> str:
 5        """
 6        To find the longest palindromic substring, we want to take each
 7        character in the string and then expand it by one on each side.
 8        If both of the expanded characters are the same, we can continue
 9        expanding the palindrome indefinitely.
10
11        To do this for odd sized palindromes, we set our left and right pointer
12        to be equal, and for even length palindromes, we set them one apart from
13        each other.
14        """
15        n = len(s)
16        res = ""
17        max_len = 0
18
19        def expand(l, r):
20            nonlocal n, res, max_len
21            while l >= 0 and r < n and s[l] == s[r]:
22                if r - l + 1 > max_len:
23                    res = s[l : r + 1]
24                    max_len = r - l + 1
25                l -= 1
26                r += 1
27
28        for i in range(n):
29            # expand from the center
30            l, r = i, i
31            expand(l, r)
32            l, r = i, i + 1
33            expand(l, r)
34
35        return res

To find the longest palindromic substring, we want to take each character in the string and then expand it by one on each side. If both of the expanded characters are the same, we can continue expanding the palindrome indefinitely.

To do this for odd sized palindromes, we set our left and right pointer to be equal, and for even length palindromes, we set them one apart from each other.

def test(): View Source

41def test():
42    assert 2 + 2 == 4