23.10.28 Today’s Leetcode

5. Longest Palindromic Substring (medium)

Brute Force with O(n^3)

class Solution:
    def longestPalindrome(self, s: str) -> str:

        def isPalindrome(text):
            return text == text[::-1]

        n = len(s)
        res = ''
        for i in range(n):
            for j in range(i, n + 1):
                cur = s[i:j]
                # print(cur)
                if isPalindrome(cur):
                    if len(cur) > len(res):
                        res = cur

        return res

Sliding window : O(n^2)

class Solution:
    def longestPalindrome(self, s: str) -> str:

        n = len(s)

        def check(index, pos=0):
            a, b = index, index + pos
            while a >= 0 and b < n and s[a] == s[b]:
                # print(s[a:b + 1])
                a -= 1
                b += 1

            return s[a + 1:b]
        
        res = ''
        for i in range(n):
            a, b = check(i), check(i, 1)
            if len(a) > len(res): res = a
            if len(b) > len(res): res = b
            
        return res

1220. Count Vowels Permutation (hard)

DP Solution

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        endsWith = {}
        chars = set(['a', 'e', 'i', 'o', 'u'])
        for char in chars:
            endsWith[char] = 1

        for step in range(n - 1):
            new_endsWith = {}
            new_endsWith['a'] = endsWith['e']
            new_endsWith['e'] = endsWith['a'] + endsWith['i']
            new_endsWith['i'] = endsWith['a'] + endsWith['e'] + endsWith['o'] + endsWith['u']
            new_endsWith['o'] = endsWith['i'] + endsWith['u']
            new_endsWith['u'] = endsWith['a']
            endsWith = new_endsWiths

        MOD = 10 ** 9 + 7

        return sum(endsWith.values()) % MOD