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])