# Posts tagged as “Palindrome”

You are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

palindrome is a string that reads the same forward and backward.

Example 1:

Input: words = ["lc","cl","gg"]
Output: 6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.
Note that "clgglc" is another longest palindrome that can be created.


Example 2:

Input: words = ["ab","ty","yt","lc","cl","ab"]
Output: 8
Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8.
Note that "lcyttycl" is another longest palindrome that can be created.


Example 3:

Input: words = ["cc","ll","xx"]
Output: 2
Explanation: One longest palindrome is "cc", of length 2.
Note that "ll" is another longest palindrome that can be created, and so is "xx".


Constraints:

• 1 <= words.length <= 105
• words[i].length == 2
• words[i] consists of lowercase English letters.

## Solution: Match mirrored words

For any pair of mirrored words, e.g. ‘ab’ <-> ‘ba’ or ‘aa’ <-> ‘aa’, we can extend the existing longest palindrome, ans += 4.
For any unpaired words with same letter, e.g. ‘cc’, we can only use one and put in the middle of the pladrome, ans += 2.

Time complexity: O(n)
Space complexity: O(26*26)

## C++

Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

palindrome is a string that reads the same forwards and backwards.

subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

Example 1:

Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")


Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".


Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")


Constraints:

• 3 <= s.length <= 105
• s consists of only lowercase English letters.

## Solution: Enumerate first character of a palindrome

For a length 3 palindrome, we just need to enumerate the first character c.
We found the first and last occurrence of c in original string and scan the middle part to see how many unique characters there.

e.g. aabca
Enumerate from a to z, looking for a*a, b*b, …, z*z.
For a*a, aabca, we found first and last a, in between is abc, which has 3 unique letters.
We can use a hastable or a bitset to track unique letters.

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

## C++

Given an array of strings words, return the first palindromic string in the array. If there is no such string, return an empty string "".

A string is palindromic if it reads the same forward and backward.

Example 1:

Input: words = ["abc","car","ada","racecar","cool"]
Explanation: The first string that is palindromic is "ada".
Note that "racecar" is also palindromic, but it is not the first.


Example 2:

Input: words = ["notapalindrome","racecar"]
Output: "racecar"
Explanation: The first and only string that is palindromic is "racecar".


Example 3:

Input: words = ["def","ghi"]
Output: ""
Explanation: There are no palindromic strings, so the empty string is returned.


Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists only of lowercase English letters.

## Solution: Brute Force

Enumerate each word and check whether it’s a palindrome or not.

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

## C++

You are given two strings, word1 and word2. You want to construct a string in the following manner:

• Choose some non-empty subsequence subsequence1 from word1.
• Choose some non-empty subsequence subsequence2 from word2.
• Concatenate the subsequences: subsequence1 + subsequence2, to make the string.

Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.

subsequence of a string s is a string that can be made by deleting some (possibly none) characters from s without changing the order of the remaining characters.

palindrome is a string that reads the same forward as well as backward.

Example 1:

Input: word1 = "cacb", word2 = "cbba"
Output: 5
Explanation: Choose "ab" from word1 and "cba" from word2 to make "abcba", which is a palindrome.

Example 2:

Input: word1 = "ab", word2 = "ab"
Output: 3
Explanation: Choose "ab" from word1 and "a" from word2 to make "aba", which is a palindrome.

Example 3:

Input: word1 = "aa", word2 = "bb"
Output: 0
Explanation: You cannot construct a palindrome from the described method, so return 0.

Constraints:

• 1 <= word1.length, word2.length <= 1000
• word1 and word2 consist of lowercase English letters.

## Solution: DP

Let s = word1 + word2, build dp table on s. We just need to make sure there’s at least one char from each string.

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

## C++

O(m+n) Space complexity

## C++

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)