python-programs/longest_palindromic_substring.py at main · haz-95/python-programs · GitHub

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution:
    def longestPalindrome(self, s: str) -> str:
        # Two pointer approach , time complexity O(n), space complexity O(1)
        max_len = -float("inf")
        max_ind = [-1, -1]

        # odd lenth palindromes
        for k in range(len(s)):
            i = k
            j = k
            while(i >= 0 and j <= len(s) - 1):
                if s[i] == s[j]:
                    if (j - i + 1) > max_len:
                        max_len = j - i + 1
                        max_ind = [i, j]

                    i -= 1
                    j += 1

                else:
                    break

        # even lenth palindromes
        for k in range(len(s) - 1):
            i = k
            j = k + 1
            while(i >= 0 and j <= len(s) - 1):
                if s[i] == s[j]:
                    if (j - i + 1) > max_len:
                        max_len = j - i + 1
                        max_ind = [i, j]

                    i -= 1
                    j += 1

                else:
                    break

        return s[max_ind[0]:max_ind[1] + 1]

        # Dynamic Programming approach ,
        # Time complexity O(n^2), Space complexity O(n^2)

        dp = [[0 for _ in range(len(s))] for _ in range(len(s))]

        # sub string of length 1
        for i in range(len(s)):
            dp[i][i] = 1

        # substring of length 1 id always a palindrome
        max_len = 1
        max_ind = [0, 0]

        # sub string of length 2
        for i in range(len(s) - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = 1
                if max_len == 1:
                    max_len = 2
                    max_ind[0] = i
                    max_ind[1] = i + 1

        # sub string of length greater than 2
        for j in range(2, len(s)):
            for i in range(0, len(s) - j):
                k = j + i
                if (s[k] == s[i]) and (dp[i + 1][k - 1] == 1):
                    dp[i][k] = 1
                    if (k - i + 1) > max_len:
                        max_len = k - i + 1
                        max_ind = [i, k]

        return s[max_ind[0]:max_ind[1] + 1]