aboutsummaryrefslogtreecommitdiff
path: root/longest_palindromic_substr.py
blob: 53726298c7b0b9344f832212d3b107133ccea0d3 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 5. Longest Palindromic Substring

"""
given a string 's', return the longest palindromic substring in 's'
"""


class Solution(object):
    def helper(self, s, l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l + 1 : r]

    def longestPalindrome(self, s):
        ans = ""
        for i in range(len(s)):
            tmp = self.helper(s, i, i)
            if len(tmp) > len(ans):
                ans = tmp
            tmp = self.helper(s, i, i + 1)
            if len(tmp) > len(ans):
                ans = tmp
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.longestPalindrome("babad"))  # expect: bab
    print(obj.longestPalindrome("cbbd"))  # expect: bb