Palindrome tester

You sit down for a phone screen at Oracle and the interviewer opens with a warm-up: "Given a string, tell me if it's a palindrome." It sounds simple, and it is, but this problem (also known as Valid Palindrome on other platforms) is one of those deceptively clean questions that reveals how well you handle string indexing, edge cases, and writing tight loops. Get it right quickly and you set the tone for the rest of the interview.

TL;DR

Use two pointers starting from opposite ends of the string. Compare characters at each position after converting to the same case. If any pair mismatches, return false immediately. If all pairs match through the middle, it's a palindrome. This runs in O(n) time and O(1) space.

Why This Problem Matters

Palindrome checking is often the first string problem candidates encounter in interview prep. It introduces the two-pointer pattern, which shows up in dozens of harder problems: container with most water, three-sum, trapping rain water, and more. Nail this pattern here, and those problems become much more approachable.

Understanding the Problem

A palindrome reads the same forward and backward. "madam" is a palindrome. "hello" is not.

We need to write a method that:

• Takes a string as input
• Returns true if the string is a palindrome, false otherwise
• Ignores case when comparing characters ("mAdaM" counts as a palindrome)

isPalindrome("madam")  -> true
isPalindrome("mAdaM")  -> true
isPalindrome("i i I")  -> true
isPalindrome("1232 1") -> false
isPalindrome("")       -> true

Edge Cases

1. Empty string: A palindrome by definition (nothing to contradict)
2. Single character: Always a palindrome
3. Even vs odd length: Both work with the same algorithm since the middle character of an odd-length string doesn't need comparison
4. Mixed case: "RaceCar" should return true

Solution Approach

The brute-force way is to reverse the string and compare it to the original. That works, but it creates a new string and uses O(n) extra space.

A better approach: compare characters from both ends, walking inward. If every pair matches, the string is a palindrome. If any pair doesn't match, we can stop immediately.

Here's how the comparison flows for "madam":

Position 0 compares m with m (index 4). Position 1 compares a with a (index 3). Position 2 is the middle of a 5-character string, so we're done. All pairs matched.

Now compare with "hello", which fails fast:

The very first comparison, h vs o, is a mismatch. We return false without checking any other characters.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public boolean isPalindrome(String str) {
    // Empty or single-char strings are palindromes
    if (str.length() <= 1) {
      return true;
    }

    int len = str.length();

    // Compare characters from both ends toward the middle
    for (int i = 0; i < len / 2; i++) {
      if (Character.toUpperCase(str.charAt(i)) !=
          Character.toUpperCase(str.charAt(len - 1 - i))) {
        return false;
      }
    }

    return true;
  }
}

Let's walk through the code:

1. Base case: If the string has 0 or 1 characters, it's trivially a palindrome
2. Loop from 0 to the midpoint: We only need to check half the string
3. Compare with case conversion: Character.toUpperCase() normalizes both characters before comparing
4. Early exit on mismatch: The moment we find a pair that doesn't match, we're done

For case-insensitive matching, here's how "mAdaM" plays out:

Both m and M become M after toUpperCase(). Same for A and a. Every pair matches, so the method returns true.

Complexity Analysis

Time: O(n) where n is the string length. We compare at most n/2 character pairs, and each comparison is O(1). In the worst case (actual palindromes), we examine every pair. In the best case (mismatch at the edges), we check just one pair.

Space: O(1). We use a loop counter and a length variable. No extra arrays, no string copies, no additional data structures.

Why Not Reverse the String?

The reversal approach looks like this:

// Works, but wastes space
return str.equalsIgnoreCase(new StringBuilder(str).reverse().toString());

This creates a reversed copy of the string (O(n) space), then compares all n characters. Our two-pointer approach is strictly better: same time, less space, and the ability to short-circuit on early mismatches.

Common Pitfalls

1. Forgetting case conversion: Comparing 'm' directly to 'M' returns false. Always normalize before comparing.

2. Off-by-one in the loop bound: Using i <= len / 2 instead of i < len / 2 causes an unnecessary comparison of the middle character with itself for odd-length strings. Not wrong, but wasteful.

3. Using == on String objects: In Java, charAt() returns primitive char, so == works fine here. But if you were comparing String objects, you'd need .equals().

Interview Tips

When presenting this solution:

• Start by confirming the constraints: case sensitivity, character types, empty strings
• Mention the two-pointer pattern by name. Interviewers like hearing you recognize patterns.
• Draw the string with index markers: m(0) a(1) d(2) a(3) m(4) and show the comparison pairs
• Note that you're iterating only half the string, not all of it
• If asked for a follow-up, mention the variant where you skip non-alphanumeric characters (LeetCode 125)

Key Takeaways

• The two-pointer technique compares characters from both ends toward the center, running in O(n) time and O(1) space.
• Always normalize case before comparing. Character.toUpperCase() or toLowerCase() handles this in one call.
• Empty strings and single characters are palindromes by definition. Handle them as a base case before entering the loop.
• This problem introduces the two-pointer pattern, which is foundational for harder problems like three-sum, container with most water, and trapping rain water.
• Early termination on the first mismatch means the best case is O(1), not O(n). Mention this tradeoff in interviews.

Practice and Related Problems

Once you're comfortable with basic palindrome checking, try these progressions:

• Palindrome number tester (no string conversion allowed)
• Palindrome linked list (reverse half and compare)
• Longest palindromic substring (expand around center)

This problem and hundreds of others are available on Firecode, where consistent daily practice helps you build the pattern recognition that top tech companies look for. Whether you're warming up for phone screens or preparing for on-site interviews, starting with fundamentals like this sets you up well.

Solutions in Other Languages

Python

class Solution:
    def is_palindrome(self, string):
        if len(string) <= 1:
            return True

        string_len = len(string)

        for i in range(string_len // 2):
            if string[i].upper() != string[string_len - 1 - i].upper():
                return False

        return True

JavaScript

class Solution {
  isPalindrome(str) {
    if (str.length <= 1) {
      return true;
    }

    const len = str.length;

    for (let i = 0; i < len / 2; i++) {
      if (str[i].toUpperCase() !== str[len - 1 - i].toUpperCase()) {
        return false;
      }
    }

    return true;
  }
}

TypeScript

class Solution {
  isPalindrome(str: string): boolean {
    if (str.length <= 1) {
      return true;
    }

    const len = str.length;

    for (let i = 0; i < len / 2; i++) {
      if (str[i].toUpperCase() !== str[len - 1 - i].toUpperCase()) {
        return false;
      }
    }

    return true;
  }
}

C++

#include <string>

class Solution {
public:
  bool isPalindrome(std::string str) {
    if (str.length() <= 1) {
      return true;
    }

    auto len = str.length();

    for (size_t i = 0; i < len / 2; i++) {
      if (::toupper(str[i]) != ::toupper(str[len - 1 - i])) {
        return false;
      }
    }

    return true;
  }
};

Go

package solution

import "strings"

func (s *Solution) IsPalindrome(str string) bool {
    if len(str) <= 1 {
        return true
    }

    upper := strings.ToUpper(str)
    size := len(upper)

    for i := 0; i < size/2; i++ {
        if upper[i] != upper[size-1-i] {
            return false
        }
    }

    return true
}

Scala

class Solution {
  def isPalindrome(str: String): Boolean = {
    if (str.length <= 1) {
      return true
    }

    val len = str.length

    for (i <- 0 until len / 2) {
      if (str(i).toUpper != str(len - 1 - i).toUpper) {
        return false
      }
    }

    true
  }
}

Kotlin

class Solution {
    fun isPalindrome(str: String): Boolean {
        if (str.length <= 1) {
            return true
        }

        val len = str.length

        for (i in 0 until len / 2) {
            if (str[i].uppercaseChar() != str[len - 1 - i].uppercaseChar()) {
                return false
            }
        }

        return true
    }
}

Swift

class Solution {
    func isPalindrome(_ str: String) -> Bool {
        if str.count <= 1 {
            return true
        }

        let chars = Array(str)
        let len = chars.count

        for i in 0..<(len / 2) {
            if chars[i].uppercased() != chars[len - 1 - i].uppercased() {
                return false
            }
        }

        return true
    }
}

Rust

impl Solution {
    pub fn is_palindrome(&self, s: String) -> bool {
        if s.len() <= 1 {
            return true;
        }

        let chars: Vec<char> = s.chars().collect();
        let len = chars.len();

        for i in 0..len / 2 {
            if chars[i].to_uppercase().next() != chars[len - 1 - i].to_uppercase().next() {
                return false;
            }
        }

        true
    }
}

C#

public class Solution {
    public bool isPalindrome(string str) {
        if (str.Length <= 1) {
            return true;
        }

        var len = str.Length;

        for (int i = 0; i < len / 2; i++) {
            if (char.ToUpper(str[i]) != char.ToUpper(str[len - 1 - i])) {
                return false;
            }
        }

        return true;
    }
}

Dart

class Solution {
  bool isPalindrome(String str) {
    if (str.length <= 1) {
      return true;
    }

    int len = str.length;

    for (int i = 0; i < len ~/ 2; i++) {
      if (str[i].toUpperCase() != str[len - 1 - i].toUpperCase()) {
        return false;
      }
    }

    return true;
  }
}

PHP

class Solution {
    public function isPalindrome(string $str): bool {
        if (strlen($str) <= 1) {
            return true;
        }

        $len = strlen($str);

        for ($i = 0; $i < intdiv($len, 2); $i++) {
            if (strtoupper($str[$i]) !== strtoupper($str[$len - 1 - $i])) {
                return false;
            }
        }

        return true;
    }
}

Ruby

class Solution
  def is_palindrome(str)
    return true if str.length <= 1

    len = str.length

    (0...len / 2).each do |i|
      return false if str[i].upcase != str[len - 1 - i].upcase
    end

    true
  end
end