125. Valid Palindrome I & II

Reference: 125. Valid Palindrome & 680. Valid Palindrome II EPI 6.5
Difficulty: Easy

My Post: Java Solutions to Valid Palindrome I & II with Explanation (SubPalindrome, Iteration & Recursion)

Problem

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example:

Input: "aba"
Output: True

Input: "race a car"
Output: false

Follow up: Do not use extra space. Also, check out Valid Palindrome II section.

Analysis

Brute-Force

The basic idea is based on the following code:

public boolean isPalindrome(String s) {
  int n = s.length();
  for (int i = 0; i < n / 2; ++i) { // n / 2 is right-leaning
    int j = n - i - 1;
    if (s.charAt(i) != s.charAt(j)) return false;
  }
  return true;
}

Since the input has some non-alphanumeric characters, we have to do some preprocessing.

• Remove invalid characters (Character.isLetterOrDigit(ch)).
• Convert all letters to lower cases (use s.toLowerCase()).
• Reversing is optional (it also incurs extra space usage).

Note:

• Since the StringBuilder is resizable, the condition in while-loop is idx < sb.length() instead of idx < n.
• Remember to update the length n after preprocessing.

public boolean isPalindrome(String s) {
  StringBuilder sb = new StringBuilder(s.toLowerCase()); // for later comparisons
  int idx = 0;  
  // remove non-letter character
  while (idx < sb.length()) {
    char ch = sb.charAt(idx);
    if (Character.isLetterOrDigit(ch)) { // letter or digit
      idx += 1;
    } else { // not letter
      sb.deleteCharAt(idx);
    }
  }
  int n = sb.length(); // update length
  // check
  for (int i = 0; i < n / 2; ++i) { // right-leaning
    int j = n - i - 1;
    if (sb.charAt(i) != sb.charAt(j)) {
      return false;
    }
  }
  return true;
}

Time: $O(N)$
Space: $O(N)$

Two Pointers

We use two indices (pointers) to traverse the string, one forwards, the other backwards, skipping nonalphanumeric characters, performing case-insensitive comparison on the alphanumeric characters. We return false as soon as there is a mismatch. If the indices cross, we have a verified palindrome string.

Note: Remember to update lo and hi at the end of each iteration.

public boolean isPalindrome(String s) {
  int lo = 0, hi = s.length() - 1;
  while (lo < hi) { // if lo >= hi, stops!
    // i stops at a letter, or lo == hi
    while (lo < hi && !isValid(s.charAt(lo))) lo += 1;
    // j stops at a letter, or lo == hi
    while (lo < hi && !isValid(s.charAt(hi))) hi -= 1;
    // check
    if (lo < hi) { // ensure in-bound & letter comparison (because they don't meet yet)
      if (isCharDiff(s.charAt(lo), s.charAt(hi))) return false;
    }
    lo += 1; hi -= 1; // update, remember to move (otherwise it caseus infinite loop)
  }
  return true;
}

private boolean isValid(char ch) {
  return Character.isLetterOrDigit(ch);
}

private boolean isCharDiff(char ch1, char ch2) {
  return Character.toLowerCase(ch1) != Character.toLowerCase(ch2);
}

Time: $O(N)$
Space: $O(1)$

Valid Palindrome II

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome. In other words, we allow one mismatch.

Note: The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

Example:

Input: "aba"
Output: True

Input: "abca"
Output: True (delete "c")

Input: "abbbca"
Output: True (delete "c")

Brute-Force

Delete each character and then test palindromicity.

Time: $O(N^2)$
Space: $O(1)$

SubPalindrome (Iteration)

When detecting the first mismatch we should consider two cases:

• Case 1: Delete the character on the left, and move on.
• Case 2: Delete the character on the right, and move on.

Then we get rid of the characters we have checked before, and only focus on those substrings in two cases. If the first case fails, we will try the second case. If it also fails, return false.

Notice that when a mismatch is detected in for-loop, every future work would be done within the current iteration.

Example: [a b b b c a]
i = left, j = right
[a b b b c a]
 i         j
[a b b b c a]
   i     j     <-- mismatch

Case 1:
[a b b b c a]
     i   j     <-- now we focus on a substring [b b c] --> fail in case 1

Case 2:
[a b b b c a]
   i   j       <-- now we focus on a substring [b b b] --> succeed in case 2

Show me the code:

// "abbbca"
public boolean validPalindrome(String s) {
  int n = s.length();
  for (int i = 0; i < n / 2; ++i) {
    int left = i, right = n - i - 1;
    if (s.charAt(left) != s.charAt(right)) { // give a last chance
      // delete char at left
      if (validSubPalindrome(s, left + 1, right)) return true;
      // delete char at right
      return validSubPalindrome(s, left, right - 1);
    }
  }
  return true;
}

private boolean validSubPalindrome(String s, int lo, int hi) {
  int n = hi - lo + 1;
  for (int i = 0; i < n / 2; ++i) {
    int left = lo + i, right = hi - i;
    if (s.charAt(left) != s.charAt(right)) return false;
  }
  return true;
}

Time: $O(N)$ since there are at most $\sim 2N$ operations.
Space: $O(1)$

SubPalindrome (Recursion)

Based on the idea above, we can write a recursive version.

Note: You have to pass down a used variable to indicate if the remedy has been used.

public boolean validPalindrome(String s) {
  return validSubPalindrome(s, 0, s.length() - 1, false);
}

private boolean validSubPalindrome(String s, int lo, int hi, boolean used) {
  if (lo >= hi) { // base case
    return true;
  }
  
  if (s.charAt(lo) != s.charAt(hi)) { // equal
    if (used == false) {
      if (validSubPalindrome(s, lo + 1, hi, true)) return true; // test left deletion
      return validSubPalindrome(s, lo, hi - 1, true); // test right deletion
    } else {
      return false;
    }
  }
  
  return validSubPalindrome(s, lo + 1, hi - 1, used);
}

Time: $O(N)$
Space: $O(N)$