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(n2) with n is the length of the given string
Space complexity: O(1)

References

Algorithm