Palindrome

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

• Time O(n^2), Space O(1)

• 2 condition: symmetric or none-symmetric

class Solution:
    def longestPalindrome(self, s: str) -> str: 
        ans = ''
        
        for i in range(len(s)):
            str1 = self.helper(s, i, i)
            str2 = self.helper(s, i, i+1)
            cand = str1 if len(str1) > len(str2) else str2
            if len(cand) > len(ans):
                ans = cand
        
        return ans
    
    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]
    

647. Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string.

def countSubstrings(self, s: str) -> int:
    count = 0
    for i in range(len(s)):
        count += self.helper(s, i, i)
        count += self.helper(s, i, i+1) 
    return count

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

131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

def partition(self, s: str) -> List[List[str]]:
    memo = {}
    memo[len(s)] = [[]]
    res = []
    return self.backtrack(0, s, memo)

def backtrack(self, start, s, memo):
    if start in memo:
        return memo[start]
    
    li = []
    for end in range(start+1, len(s)+1):
        cand = s[start: end]
        if self.isValid(cand):
            for suffix in self.backtrack(end, s, memo):
                li.append([cand] + suffix)
    memo[start] = li
    return li
    
def isValid(self, s):
    i, j = 0, len(s)-1
    while i < j:
        if s[i] != s[j]: return False
        i+=1
        j-=1
    return True

132. Palindrome Partitioning II

Given a string s, cut s into some substrings such that every substring is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Sequence DP

• State: f[i]代表前i項中最小可以分成幾個

• Func: f[i]=min{f[j]+1}, j<i && String(j,i) is Palindrom

• Init: f[i] = i

• Ans: f[i]-1, n個切n-1刀

def minCut(self, s: str) -> int:
    n = len(s) + 1
    dp = [float('inf')] * n
    dp[0] = 0
    
    for i in range(1, n):
        for j in range(i+1):
            cand = s[j:i]
            if self.isValid(cand):
                dp[i] = min(dp[i], dp[j] + 1)
    # print(dp)     
    return dp[n-1] - 1


def isValid(self, s):
    i, j = 0, len(s)-1
    while i < j:
        if s[i] != s[j]: return False
        i += 1
        j -= 1
        
    return True

每次check valid palindrome 可以用 memo 紀錄著

def minCut(self, s: str) -> int:
    n = len(s)
    cut = [0] * n
    memo = [[False] * n for _ in range(n)]
    
    for i in range(n):
        min_cut = i
        for j in range(i+1):
            if s[j] == s[i] and (i - j < 2 or memo[j+1][i-1]):
                memo[j][i] = True
                min_cut = min(min_cut, cut[j-1]+1) if j !=0 else 0
                
        cut[i] = min_cut
        
    return cut[n-1]

267. Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

• Take left half of palindrome and make a permutation

def generatePalindromes(self, s: str) -> List[str]:
    counter = collections.Counter(s)
    
    single = ''
    pool = ''
    
    for char, count in counter.items():
        if count%2 == 1:
            if single:
                return []
            else:
                single = char
        pool += count//2 * char
        
    li = list(pool)
    li.sort()
    
    half = self.getPermutation(li)
    
    return [h + single + h[::-1] for h in half]


def getPermutation(self, li):
    visited = [False] * len(li)
    res = []
    self.backtrack([], li, visited, res)
    return res


def backtrack(self, cand, li, visited, res):
    if len(cand) == len(li):
        res.append(''.join(cand))
        return 
    
    for i in range(len(li)):
        if visited[i] or i > 0 and (li[i] == li[i-1] and visited[i-1] == False): continue
        visited[i] = True
        self.backtrack(cand + [li[i]], li, visited, res)
        visited[i] = False

214. Shortest Palindrome

Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

"""
Brute force
reverse string r, 比較 r 後半部是某相等於 s, return (r 前半部 + s)
"""
def shortestPalindrome(self, s: str) -> str:
    r = s[::-1]
    for i in range(len(s)+1):
        if s.startswith(r[i:]):
            return r[:i] + s 

516. Palindromic Subsequence

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.

• Diagonal DP

• DP[i][j] = string[i:j] 為最長palindrome 的長度

def longestPalindromeSubseq(self, s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    for i in range(n-1, -1, -1):
        dp[i][i] = 1
        for j in range(i+1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

O(2*n) space

def longestPalindromeSubseq(self, s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(2)]
    
    for i in range(n-1, -1, -1):
        dp[i%2][i] = 1
        for j in range(i+1, n):
            if s[i] == s[j]:
                dp[i%2][j] = dp[(i+1)%2][j-1] + 2
            else:
                dp[i%2][j] = max(dp[(i+1)%2][j], dp[i%2][j-1])
    return dp[0][n-1]

1312. Minimum Insertion Steps to Make a String Palindrome

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

"""
Find the length of longest subsequence palindrome
The rest of char would be need to be insterted
"""
def minInsertions(self, s: str) -> int:
    n = len(s)
    dp = [[0] * len(s) for _ in range(2)]
    
    for i in range(n-1, -1, -1):
        dp[i%2][i] = 1
        for j in range(i+1, n):
            if s[i] == s[j]:
                dp[i%2][j] = dp[(i+1)%2][j-1] + 2
            else:
                dp[i%2][j] = max(dp[(i+1)%2][j], dp[i%2][j-1])
    
    return n - dp[0][n-1]

1297. Maximum Number of Occurrences of a Substring

Given a string s, return the maximum number of ocurrences of any substring under the following rules:

• The number of unique characters in the substring must be less than or equal to maxLetters.

• The substring size must be between minSize and maxSize inclusive.

Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: Substring "aaa" occur 2 times in the string. It can overlap.

"""
Consider answer must comes from substring with minSize, we don't need maxSize
"""
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
    record = collections.defaultdict(int)
    
    for i in range(len(s) - minSize + 1):
        record[s[i:i+minSize]] += 1
        
    return max([v for k, v in record.items() if len(set(k)) <= maxLetters] + [0])