> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/2.1-string/palindrome-partition.md).

# 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

```java
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.

```python
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.

```python
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刀

```python
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 紀錄著

```python
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

```python
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.

```python
"""
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 的長度

```python
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

```python
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.

```python
"""
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.

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

```python
"""
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])
```