# Posts tagged as “Palindrome”

You are given two strings a and b of the same length. Choose an index and split both strings at the same index, splitting a into two strings: aprefix and asuffix where a = aprefix + asuffix, and splitting b into two strings: bprefix and bsuffix where b = bprefix + bsuffix. Check if aprefix + bsuffix or bprefix + asuffix forms a palindrome.

When you split a string s into sprefix and ssuffix, either ssuffix or sprefix is allowed to be empty. For example, if s = "abc", then "" + "abc""a" + "bc""ab" + "c" , and "abc" + "" are valid splits.

Return true if it is possible to form a palindrome string, otherwise return false.

Notice that x + y denotes the concatenation of strings x and y.

Example 1:

Input: a = "x", b = "y"
Output: true
Explaination: If either a or b are palindromes the answer is true since you can split in the following way:
aprefix = "", asuffix = "x"
bprefix = "", bsuffix = "y"
Then, aprefix + bsuffix = "" + "y" = "y", which is a palindrome.


Example 2:

Input: a = "abdef", b = "fecab"
Output: true


Example 3:

Input: a = "ulacfd", b = "jizalu"
Output: true
Explaination: Split them at index 3:
aprefix = "ula", asuffix = "cfd"
bprefix = "jiz", bsuffix = "alu"
Then, aprefix + bsuffix = "ula" + "alu" = "ulaalu", which is a palindrome.


Example 4:

Input: a = "xbdef", b = "xecab"
Output: false


Constraints:

• 1 <= a.length, b.length <= 105
• a.length == b.length
• a and b consist of lowercase English letters

## Solution: Greedy

Try to match the prefix of A and suffix of B (or the other way) as much as possible and then check whether the remaining part is a palindrome or not.

e.g. A = “abcxyzzz”, B = “uuuvvcba”
A’s prefix abc matches B’s suffix cba
We just need to check whether “xy” or “vv” is palindrome or not.
The concatenated string “abc|vvcba” is a palindrome, left abc is from A and vvcba is from B.

Time complexity: O(n)
Space complexity: O(1)

## C++

Given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string, if it is generated by deleting some characters of a given string without changing its order.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

Input: s = "ababa"
Output: 1


Example 2:

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "".
Remove palindromic subsequence "a" then "bb".


Example 3:

Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "".
Remove palindromic subsequence "baab" then "b".


Example 4:

Input: s = ""
Output: 0


Constraints:

• 0 <= s.length <= 1000
• s only consists of letters ‘a’ and ‘b’

## Solution: Math

if s is empty => 0 step
if s is a palindrome => 1 step
Otherwise, 2 steps…
1. delete all the as
2. delete all the bs

Time complexity: O(n)
Space complexity: O(n) / O(1)

## C++

Given a palindromic string palindrome, replace exactly one character by any lowercase English letter so that the string becomes the lexicographically smallest possible string that isn’t a palindrome.

After doing so, return the final string.  If there is no way to do so, return the empty string.

Example 1:

Input: palindrome = "abccba"
Output: "aaccba"


Example 2:

Input: palindrome = "a"
Output: ""


Constraints:

• 1 <= palindrome.length <= 1000
• palindrome consists of only lowercase English letters.

## Solution: Greedy

For the first half of the string, replace the first non ‘a’ character to ‘a’.

e.g. abcdcba => aacdcba

If not found which means the the entire string is ‘a’ expect the middle one if the length is odd, like aa or aba, replace the last character to ‘b’.

aa => ab
aba => abb

Time complexity: O(n)
Space complexity: O(1)

## C++

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.

Palindrome String is one that reads the same backward as well as forward.

Example 1:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.


Example 2:

Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".


Example 3:

Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".


Example 4:

Input: s = "g"
Output: 0


Example 5:

Input: s = "no"
Output: 1


Constraints:

• 1 <= s.length <= 500
• All characters of s are lower case English letters.

## Solution: DP

dp[i][j] := min chars to insert
dp[j][j] = dp[i-1][j+1] if s[i] == s[j] else min(dp[i+1][j] , dp[i][j-1]) + 1
base case: dp[i][i] = 0
ans: dp[n-1]

Time complexity: O(n^2)
Space complexity: O(n^2)

## C++

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

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

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

## Solution: DP

dp[i] := min cuts of s[0~i]
dp[i] = min{dp[j] + 1} if s[j+1~i] is a palindrome.

Time complexity: O(n^2)
Space complexity: O(n^2)

DP v2

## Related Problems

Mission News Theme by Compete Themes.