Backend interview prep

Start Learning

Palindrome String

Java coding interview problem for String Coding: Palindrome String.

Checking whether a string is a Palindrome is one of the most frequently asked string problems in Java coding interviews.

Although the problem appears simple, interviewers use it to evaluate your understanding of:

  • String manipulation
  • Character comparison
  • Two Pointer Algorithm
  • Time Complexity
  • Space Optimization
  • Recursion
  • Edge Case Handling

Most interviewers start with the basic problem and gradually increase the difficulty by asking questions like:

  • Can you solve it without reversing the string?
  • Can you ignore spaces and punctuation?
  • Can you ignore uppercase and lowercase letters?
  • Which approach uses the least memory?
  • How would you handle Unicode characters?

Understanding multiple approaches prepares you for all these interview scenarios.

Problem Statement

Given a string, determine whether it reads the same from left to right and right to left.

Return:

  • true if the string is a palindrome.
  • false otherwise.

Example 1

Input

madam

Output

true

Example 2

Input

level

Output

true

Example 3

Input

hello

Output

false

Example 4

Input

racecar

Output

true

What is a Palindrome?

A palindrome is a sequence that remains exactly the same when read in reverse order.

Examples

madam

Reverse

madam

Same?

Yes

Another Example

racecar

Reverse

racecar

Same?

Yes

Non-palindrome

hello

Reverse

olleh

Same?

No

Why is Palindrome Asked in Interviews?

Palindrome is considered a foundational problem in string algorithms.

Interviewers use it to evaluate whether candidates understand:

  • String indexing
  • Character comparison
  • Looping
  • Two Pointer Algorithm
  • Recursion
  • Space optimization
  • Edge cases

It is also the basis for many advanced interview questions.

Examples

  • Valid Palindrome
  • Longest Palindromic Substring
  • Palindrome Number
  • Palindrome Linked List
  • Partition String into Palindromes

Real-World Applications

Palindrome algorithms are used in several practical applications.

DNA Sequence Analysis

Many DNA matching algorithms compare mirrored sequences.

Natural Language Processing

Some text analysis systems identify symmetrical words and phrases.

Data Validation

Certain validation algorithms compare forward and backward data.

Cryptography

Some encoding algorithms use reversible transformations during verification.

Competitive Programming

Palindrome problems frequently appear in coding contests.

Understanding String Comparison in Java

Strings in Java consist of characters stored at consecutive indexes.

Example

String word = "LEVEL";

Memory

+---+---+---+---+---+
| L | E | V | E | L |
+---+---+---+---+---+
 0   1   2   3   4

To determine whether the string is a palindrome, compare:

First

↓

Last

Then

Second

↓

Second Last

Continue until the middle.

Case Sensitivity

A common interview follow-up question is:

Should uppercase and lowercase letters be treated as equal?

Example

Madam

Compared directly

M

↓

m

They are different characters.

Result

false

If the requirement ignores case,

convert the string first.

input = input.toLowerCase();

Then

madam

becomes a palindrome.

Special Characters

Interviewers often ask:

Should punctuation be ignored?

Example

A man, a plan, a canal: Panama

If punctuation is included,

it is not a palindrome.

If punctuation and spaces are ignored,

the processed string becomes

amanaplanacanalpanama

which is a palindrome.

We'll implement this advanced version in Part 2.

Mathematical Concept

Suppose

RADAR

Indexes

0 1 2 3 4

Characters

R A D A R

Comparisons

0 ↔ 4

1 ↔ 3

2

Notice

The middle character never needs comparison.

Only half of the string is checked.

Visual Representation

Input

LEVEL

L E V E L
↑       ↑

Match

  ↑   ↑

 Match

    ↑

Middle

Every comparison succeeds.

Result

Palindrome

Non-palindrome

HELLO

H E L L O
↑       ↑

Mismatch

Immediately return

false

Dry Run

Input

MADAM

Length

5

Iteration 1

Left = 0

Right = 4

M == M

Move pointers.

Iteration 2

Left = 1

Right = 3

A == A

Move pointers.

Iteration 3

Left = 2

Right = 2

Pointers meet.

Return

true

Input

HELLO

Iteration 1

H

↓

O

Mismatch.

Return

false

Approach 1 — Two Pointer Technique (Recommended)

The Two Pointer Technique is the most efficient and interview-preferred solution.

Instead of reversing the string, compare characters from both ends.

If every pair matches,

the string is a palindrome.

Otherwise,

it is not.

Algorithm

  1. Initialize two pointers.
  2. Left starts from index 0.
  3. Right starts from the last index.
  4. Compare both characters.
  5. If they differ, return false.
  6. Otherwise move inward.
  7. Continue until pointers meet.

Java Program

public class PalindromeString {

    public static boolean isPalindrome(String input) {

        int left = 0;
        int right = input.length() - 1;

        while (left < right) {

            if (input.charAt(left) != input.charAt(right)) {
                return false;
            }

            left++;
            right--;

        }

        return true;

    }

    public static void main(String[] args) {

        System.out.println(isPalindrome("madam"));

        System.out.println(isPalindrome("hello"));

    }

}

Output

true

false

Step-by-Step Code Explanation

Initialize the left pointer.

int left = 0;

Initialize the right pointer.

int right = input.length() - 1;

Continue while

left < right

Compare both characters.

input.charAt(left)

↓

input.charAt(right)

If they differ,

return

false;

Otherwise

move both pointers.

left++;

right--;

If every comparison succeeds,

return

true;

Dry Run of Two Pointer Technique

Input

LEVEL
Iteration Left Right Comparison Result
1 0 4 L == L Continue
2 1 3 E == E Continue
3 2 2 Pointers Meet true

Input

JAVA
Iteration Left Right Comparison Result
1 0 3 J != A false

Advantages

  • Best interview solution.
  • No string reversal required.
  • Stops immediately on mismatch.
  • Easy to understand.
  • Uses constant extra space.

Drawbacks

  • Requires manual pointer management.
  • Needs additional preprocessing if spaces, punctuation, or case should be ignored.

Approach 2 — Reverse String and Compare

Another straightforward solution is to reverse the string and compare it with the original.

If both strings are identical,

the string is a palindrome.

Algorithm

  1. Reverse the string.
  2. Compare the reversed string with the original.
  3. Return the comparison result.

Java Program

public class PalindromeUsingReverse {

    public static boolean isPalindrome(String input) {

        String reversed = new StringBuilder(input)
                .reverse()
                .toString();

        return input.equals(reversed);

    }

    public static void main(String[] args) {

        System.out.println(isPalindrome("racecar"));

        System.out.println(isPalindrome("java"));

    }

}

Output

true

false

Step-by-Step Code Explanation

Create a mutable string.

new StringBuilder(input)

Reverse the characters.

.reverse()

Convert back to String.

.toString()

Compare.

input.equals(reversed)

Returns

true

only if both strings are identical.

Time & Space Complexity

Approach Time Extra Space
Two Pointer Technique O(n) O(1)
Reverse and Compare O(n) O(n)

Where:

  • n = length of the input string.

The Two Pointer approach is generally preferred because it avoids creating a reversed copy of the string.

Comparison of Approaches

Feature Two Pointer Reverse & Compare
Interview Friendly ⭐⭐⭐⭐⭐ ⭐⭐⭐
Easy to Understand ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐
Extra Space O(1) O(n)
Stops Early on Mismatch ✅ ❌
Production Use Excellent Good

Advantages of These Approaches

  • Easy to implement.
  • Linear time complexity.
  • Foundation for advanced palindrome problems.
  • Frequently asked in Java interviews.
  • Demonstrates understanding of string traversal and comparison.

Drawbacks

  • Reverse-and-compare creates an additional string.
  • Neither approach handles case-insensitive comparisons or ignores punctuation without preprocessing.
  • Advanced scenarios such as Unicode-aware comparisons require extra handling.

In Part 2, we'll cover:

  • Approach 3 – Using Recursion
  • Approach 4 – Using Stack
  • Approach 5 – Using StringBuilder.reverse()
  • Palindrome Ignoring Spaces and Punctuation
  • Palindrome Ignoring Case
  • Unicode Considerations
  • Comparison of All Approaches
  • Common Interview Mistakes
  • Edge Cases
  • Interview Follow-up Questions
  • Related Problems
  • Key Takeaways
  • Interview Tips

Approach 3 — Using Recursion

Recursion is another elegant way to determine whether a string is a palindrome.

Instead of comparing characters using loops, recursion compares the first and last characters, then recursively checks the remaining substring.

Visualization

Input

MADAM

Recursive Calls

MADAM

↓

ADA

↓

D

↓

Empty

During the return phase:

D

↓

ADA

↓

MADAM

Every comparison succeeds.

Result

true

Algorithm

  1. Compare the first and last characters.
  2. If they are different, return false.
  3. Remove both characters.
  4. Repeat recursively.
  5. Stop when the string length becomes 0 or 1.

Java Program

public class PalindromeRecursion {

    public static boolean isPalindrome(String str) {

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

        if (str.charAt(0) != str.charAt(str.length() - 1)) {
            return false;
        }

        return isPalindrome(str.substring(1, str.length() - 1));

    }

    public static void main(String[] args) {

        System.out.println(isPalindrome("madam"));

        System.out.println(isPalindrome("hello"));

    }

}

Output

true

false

Advantages

  • Elegant implementation.
  • Demonstrates recursion skills.
  • Frequently asked in recursion interviews.

Drawbacks

  • Uses recursive call stack.
  • Creates new substrings.
  • Not recommended for very large strings.

Approach 4 — Using Stack

A Stack follows the Last-In, First-Out (LIFO) principle.

The idea is simple:

  1. Push every character.
  2. Pop one by one.
  3. Compare with the original string.

Visualization

Input

JAVA

Push

J

↓

A

↓

V

↓

A

Pop

A

↓

V

↓

A

↓

J

Reversed sequence

AVAJ

Compare

JAVA

↓

AVAJ

Not equal.

Result

false

Java Program

import java.util.Stack;

public class PalindromeStack {

    public static boolean isPalindrome(String input) {

        Stack<Character> stack = new Stack<>();

        for (char ch : input.toCharArray()) {
            stack.push(ch);
        }

        for (char ch : input.toCharArray()) {

            if (ch != stack.pop()) {
                return false;
            }

        }

        return true;

    }

    public static void main(String[] args) {

        System.out.println(isPalindrome("level"));

        System.out.println(isPalindrome("java"));

    }

}

Output

true

false

Approach 5 — Using StringBuilder.reverse()

Java provides a built-in method to reverse strings.

The algorithm:

  1. Reverse the string.
  2. Compare it with the original.

Java Program

public class PalindromeStringBuilder {

    public static boolean isPalindrome(String input) {

        String reversed = new StringBuilder(input)
                .reverse()
                .toString();

        return input.equals(reversed);

    }

    public static void main(String[] args) {

        System.out.println(isPalindrome("racecar"));

        System.out.println(isPalindrome("coding"));

    }

}

Output

true

false

Palindrome Ignoring Spaces and Punctuation

One of the most common interview follow-up questions is:

Ignore spaces, commas, punctuation, and special characters.

Example

Input

A man, a plan, a canal: Panama

After preprocessing

amanaplanacanalpanama

Output

true

Java Program

public class ValidPalindrome {

    public static boolean isPalindrome(String input) {

        input = input.replaceAll("[^a-zA-Z0-9]", "")
                     .toLowerCase();

        int left = 0;
        int right = input.length() - 1;

        while (left < right) {

            if (input.charAt(left) != input.charAt(right)) {
                return false;
            }

            left++;
            right--;

        }

        return true;

    }

    public static void main(String[] args) {

        String input = "A man, a plan, a canal: Panama";

        System.out.println(isPalindrome(input));

    }

}

Output

true

Palindrome Ignoring Case

Sometimes interviewers ask:

Ignore uppercase and lowercase differences.

Example

Input

Madam

Convert

madam

Output

true

Java Program

public class IgnoreCasePalindrome {

    public static boolean isPalindrome(String input) {

        input = input.toLowerCase();

        int left = 0;
        int right = input.length() - 1;

        while (left < right) {

            if (input.charAt(left) != input.charAt(right)) {
                return false;
            }

            left++;
            right--;

        }

        return true;

    }

}

Unicode Considerations

Most interview questions assume English letters.

However, Java stores text using Unicode.

Examples

こんにちは

😊😊

A simple char-based comparison may not correctly handle all Unicode characters because some characters (such as many emoji) are represented using surrogate pairs.

For full Unicode correctness, consider iterating over Unicode code points instead of individual char values.

Edge Cases

Input Expected Output
"" true
"a" true
"aa" true
"ab" false
"12321" true
"12345" false
" " true (after trimming/ignoring spaces, depending on requirements)
null Handle gracefully based on application requirements

Time & Space Complexity

Approach Time Extra Space
Two Pointer O(n) O(1)
Reverse & Compare O(n) O(n)
Recursion O(n) O(n)
Stack O(n) O(n)
StringBuilder.reverse() O(n) O(n)

Where:

  • n = length of the string.

The Two Pointer Technique is the most space-efficient solution.

Comparison of All Approaches

Approach Interview Friendly Extra Space Recommended
Two Pointer ⭐⭐⭐⭐⭐ O(1) ⭐⭐⭐⭐⭐
Reverse & Compare ⭐⭐⭐⭐ O(n) ⭐⭐⭐⭐
Recursion ⭐⭐⭐⭐ O(n) ⭐⭐⭐
Stack ⭐⭐⭐ O(n) ⭐⭐⭐
StringBuilder.reverse() ⭐⭐⭐ O(n) ⭐⭐⭐⭐⭐ (Production)

Common Interview Mistakes

Mistake 1

Reversing the string when the interviewer explicitly asks not to.

Preferred solution:

Two Pointer Technique

Mistake 2

Ignoring uppercase and lowercase differences.

Wrong

Madam

Correct

input.toLowerCase();

Mistake 3

Ignoring punctuation.

Wrong

A man, a plan...

Correct

replaceAll("[^a-zA-Z0-9]", "")

Mistake 4

Comparing Strings using ==.

Wrong

input == reversed

Correct

input.equals(reversed)

Mistake 5

Not handling empty strings.

Remember

Empty String

↓

Palindrome

because it reads the same forward and backward.

Interview Follow-up Questions

Q1. Can you solve it without reversing the string?

Q2. Can you ignore spaces and punctuation?

Q3. Can you ignore uppercase and lowercase letters?

Q4. What is the most efficient solution?

Q5. Can you solve it using recursion?

Q6. Can you solve it using a Stack?

Q7. How would you handle Unicode characters?

Q8. What is the time complexity?

Q9. What happens if the input is null?

Q10. Can you check whether an integer is a palindrome?

Related Problems

  • Reverse String
  • Valid Palindrome
  • Longest Palindromic Substring
  • Palindrome Number
  • Palindrome Linked List
  • Reverse Words in a String
  • Reverse Vowels of a String
  • Longest Common Prefix
  • String Compression

Key Takeaways

  • A palindrome reads the same forward and backward.
  • The Two Pointer Technique is the preferred interview solution because it uses O(1) extra space.
  • StringBuilder.reverse() is simple and suitable for production code.
  • Recursion and Stack solutions are useful for demonstrating alternative problem-solving techniques.
  • Many real-world palindrome checks require preprocessing to ignore case, spaces, and punctuation.
  • Always consider edge cases such as empty strings, single-character strings, and null inputs.
  • Unicode-aware applications should process code points instead of individual char values when necessary.

Frequently Asked Interview Questions

Q1. Why is the Two Pointer Technique preferred?

It compares characters directly from both ends without creating a copy of the string, making it efficient in both time and space.

Q2. Why shouldn't we compare strings using ==?

The == operator compares object references, not string contents.

Correct approach:

input.equals(reversed)

Q3. Can a palindrome check stop early?

Yes.

As soon as one pair of characters does not match, the algorithm immediately returns false, avoiding unnecessary comparisons.

Q4. Is an empty string a palindrome?

Yes.

An empty string reads the same in both directions, so it is considered a palindrome.

Q5. How do coding platforms like LeetCode define a valid palindrome?

Problems such as Valid Palindrome typically require:

  • Ignoring uppercase and lowercase differences.
  • Ignoring spaces.
  • Ignoring punctuation and special characters.
  • Comparing only letters and digits.

Always read the problem statement carefully before implementing the solution.

Interview Tip

If an interviewer asks:

"Check whether a string is a palindrome in Java."

Start with the Two Pointer Technique because it is the most efficient manual solution.

Explain your approach:

  1. Initialize two pointers at the beginning and end of the string.
  2. Compare characters at both pointers.
  3. If they differ, return false immediately.
  4. Otherwise, move the pointers inward.
  5. Continue until the pointers meet or cross.

After implementing the basic solution, mention advanced variations such as:

  • Ignoring case
  • Ignoring spaces and punctuation
  • Unicode-aware palindrome checking
  • Recursive implementation

Demonstrating these follow-up solutions shows a deeper understanding of string algorithms and prepares you for advanced interview discussions.