Check whether a String is Palindrome or not

The problem, simply

You get a string. Say if it is a palindrome: a word that reads the same forwards and backwards, like madam or racecar.

Return true if it is, false if it is not.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write the string backwards and check if the backwards copy is the same as the original.

1. Build the reverse of s.
2. Compare it with s, letter by letter.

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder rev = new StringBuilder();
        for (int i = s.length() - 1; i >= 0; i--) {
            rev.append(s.charAt(i));             // build the backwards copy
        }
        return s.equals(rev.toString());         // same both ways?
    }
}

How long it takes: one walk to build the copy and one to compare, O(n). Extra room: the copy is as long as the string, O(n).

Way 2: the clever way

Do what the two friends do. Use two fingers, left and right, and compare in place.

1. Put left on the first letter and right on the last.
2. While left < right: if the letters differ, return false. Otherwise move left one step right and right one step left.
3. If the loop ends, return true.

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;  // one bad pair is enough
            left++;
            right--;
        }
        return true;
    }
}

How long it takes: at most n / 2 pairs, so O(n). Extra room: two fingers, O(1). It can also stop on the very first pair, which the copy way cannot.

Another way: ignore spaces, marks and case

Interviewers love the sentence version: A man, a plan, a canal: Panama should count as a palindrome. Same two fingers, with two extra rules. A finger on something that is not a letter or digit skips over it. Letters are compared after making them lowercase.

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            // skip anything that is not a letter or digit
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Still O(n) time and O(1) room, because each finger only ever moves forward.

Watch out for

• s.equals(rev) is right. s == rev compares objects in Java, not letters, and returns false.
• In the sentence version, the skip loops need left < right too, or a string like ., runs off the end.
• Case: Madam is only a palindrome if you ignore case. Ask the interviewer.
• A recursive version, check(s, l + 1, r - 1), is neat but uses O(n) stack space and can overflow on huge strings.

What interviewers ask next

• Can you remove at most one letter to make it a palindrome? Walk the two fingers. At the first bad pair, try skipping the left letter or the right letter, and check if either rest is a palindrome. Still O(n).
• Is a number a palindrome without turning it into a string? Build the reverse of the second half of its digits with % 10 and / 10, and stop when the reversed half is at least as big as what is left.
• Is a linked list a palindrome? Find the middle with a slow and a fast pointer, reverse the second half, then walk both halves together.
• Longest palindrome inside a string? Grow outwards from every middle (each letter and each gap between letters). That takes O(n^2) time and O(1) room.
• Can the letters be rearranged into a palindrome? Count letters. At most one letter may appear an odd number of times.

Remember this

Grown-up words: the two friends are two pointers, walking toward the middle is the converging two pointer pattern, the backwards copy costs O(n) auxiliary space, and skipping marks is input normalization.