A palindrome is a string that can be read the same forward and backward such as "madam" or "racecar". A palindrome mirrors around its center. The center would be an empty character in "abba" or "e" in "racecar"

To resolve a palindrome problem, one would use frequencies counting, two pointers, or hash table algorithms

## Valid Palindrome Problem

Given a string. Remove all non-alphanumeric characters (non-letters and non-digits), convert all letters to lowercase, and return true if it is a valid palindrome or false otherwise

Example

- Input: "madAm". Output: true
- Input: "racecat". Output: false
- Input: "Was it a car or a cat I saw?". Output: true

### Approach: Two Pointers

Use two index pointers `i`

and `j`

, one starting from 0 and the other starting from the end of the string, and walk inward into the string. Return false as soon as characters at `i`

and `j`

are different

```
public boolean isPalindrome(String s) {
s = s.replaceAll("[^A-Za-z0-9]+", "").toLowerCase();
for (int i=0, j=s.length()-1; i < j;) {
if (s.charAt(i++) != s.charAt(j--)) {
return false;
}
}
return true;
}
```

In Java, besides using the replaceAll method to remove all non-alphanumeric characters, one would also use Character.isCharacterOrDigit to check each character in the given string

```
public boolean isPalindrome(String s) {
s = s.toLowerCase();
for (int i=0, j=s.length()-1; i < j;) {
if (!Character.isLetterOrDigit(s.charAt(i))) {
i++;
}
else if (!Character.isLetterOrDigit(s.charAt(j))) {
j--;
}
else if (s.charAt(i++) != s.charAt(j--)) {
return false;
}
}
return true;
}
```

Time complexity: O(n) with n is the length of the given string

Space complexity: O(1)

### Approach: Reverse and Compare

Reverse the given string and compare the reversed with the given string. Return true if it is the same or false otherwise

In Java, one would use the `reverse`

method of `StringBuilder`

to reverse a string

```
public boolean isPalindrome(String s) {
s = s.toLowerCase();
StringBuilder builder = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
builder.append(c);
}
}
return builder.toString().equals(builder.reverse().toString());
}
```

Time complexity: O(n) with n is the length of the given string

Space complexity: O(n)

## Longest Palindrome Problem

Given a string. Return the length of the longest palindrome that can be built from that string. Letters are case-sensitive, `racecAr`

is not a valid palindrome here

Example

Input: "abccccdd". Output: 7. "dccaccd" is one of the longest palindromes that can be built

Input: "a". Output: 1

### Approach: Frequencies Counting

Loop through the given string and count the frequencies of all characters. If any count equals 2, add up the count into a variable `len`

as that character can be used to build the longest palindrome string

```
public int longestPalindrome(String s) {
int[] count = new int[58];
int len = 0;
for (char c : s.toCharArray()) {
int i = c - 'A';
if (++count[i] == 2) {
len += 2;
count[i] = 0;
}
}
return Math.min(s.length(), len + 1);
}
```

the `count`

array is declared with size 58 as `'z'-'A' = 57`

If `len`

is less than `s.length()`

, one more character can be used as a center point to build the longest palindrome string

Time complexity: O(n) with n is the length of the given string

Space complexity: O(1), size of `count`

array is always constant

### Approach: Hash Set

Iterate over each character in the given string `s`

, add it into a HashSet `set`

or remove if existed. If the final HashSet is empty returns the length of the given string, otherwise returns `s.length() - set.size() + 1`

as only 1 character in the final `set`

can be used to make the center point of the palindrome string

```
public int longestPalindrome(String s) {
Set<Character> set = new HashSet<>();
for (char c : s.toCharArray()) {
if (set.contains(c)) set.remove(c);
else set.add(c);
}
return set.isEmpty() ? s.length() : s.length() - set.size() + 1;
}
```

Time complexity: O(n) with n is the length of the given string

Space complexity: O(n). HashSet may contain n characters

## Longest Palindromic Substring Problem

Given a string. Return the longest palindromic substring

Example

Input: "bananas". Output: "anana"

Input: "bb". Output: "bb"

### Approach: Expand around center

Palindrome string mirrors around its center point. The center point would be the center character `"a"`

in `"anana"`

or an empty character in `"abba"`

Thus, one would loop through the given string, extend the substring starting at each index for both above cases and track the longest palindromic substring

```
public String longestPalindrome(String s) {
String max = "";
for (int i = 0; i < s.length(); i++) {
String s1 = extendFromMiddle(s, i, i);
String s2 = extendFromMiddle(s, i, i+1);
if (s1.length() > max.length()) max = s1;
if (s2.length() > max.length()) max = s2;
}
return max;
}
public String extendFromMiddle(String s, int i, int j) {
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
return s.substring(i+1, j);
}
```

Time complexity: O(n^{2}) with n is the length of the given string

Space complexity: O(1)