Palindrome and Anagram Problems in Strings

Palindrome checks

boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        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;
}

O(n) time, O(1) space, and no new string is allocated. Reversing the string and comparing also works and is fine to mention — but it costs O(n) extra space, so lead with the two-pointer version.

Longest palindromic substring: expand around centre

Every palindrome has a centre. There are 2n-1 of them — n single characters and n-1 gaps between characters — and from each you can expand outwards while the characters match.

String longestPalindrome(String s) {
    if (s.isEmpty()) return "";
    int start = 0, end = 0;

    for (int i = 0; i < s.length(); i++) {
        int odd  = expand(s, i, i);       // centre on a character
        int even = expand(s, i, i + 1);   // centre between characters
        int len  = Math.max(odd, even);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end   = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() &&
           s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;              // length of the matched palindrome
}

O(n²) time, O(1) space. Manacher's algorithm gets to O(n), and is worth naming in an interview, but expand-around-centre is what you should be able to write from memory.

Anagram checks by counting

Two strings are anagrams when they have identical character counts. Sorting both and comparing works at O(n log n); counting works at O(n) and is the answer to give.

boolean isAnagram(String a, String b) {
    if (a.length() != b.length()) return false;   // cheap early exit

    int[] count = new int[26];
    for (int i = 0; i < a.length(); i++) {
        count[a.charAt(i) - 'a']++;
        count[b.charAt(i) - 'a']--;               // one pass over both
    }
    for (int c : count) if (c != 0) return false;
    return true;
}