Palindrome Detection in DSA Java

Mental Model

A palindrome reads the same forwards and backwards. We check if the first half matches the reversed second half.

Analogy: Like checking if a word on a mirror looks the same as the original word.

head -> [H] -> [E] -> [L] -> [L] -> [O] -> null
           ↑start                  ↑end

Dry Run Walkthrough

Input: string: "level"

Goal: Determine if the string reads the same forwards and backwards

Step 1: Set two pointers: start at first character, end at last character

start points to 'l' (index 0), end points to 'l' (index 4)

Why: We compare characters from both ends moving inward

Step 2: Compare characters at start and end pointers

'l' == 'l' -> move start to index 1, end to index 3

Why: Characters match, continue checking inner characters

Step 3: Compare characters at new start and end pointers

'e' == 'e' -> move start to index 2, end to index 2

Why: Characters match, pointers meet in the middle

Step 4: Since start and end pointers are at the same character, palindrome confirmed

start == end at 'v' (index 2)

Why: Middle character doesn't affect palindrome property

Result:

The string "level" is a palindrome

Annotated Code

DSA Java

public class PalindromeDetection {
    public static boolean isPalindrome(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false; // mismatch found, not palindrome
            }
            start++; // move start pointer forward
            end--;   // move end pointer backward
        }
        return true; // all matched, is palindrome
    }

    public static void main(String[] args) {
        String input = "level";
        boolean result = isPalindrome(input);
        if (result) {
            System.out.println("The string \"" + input + "\" is a palindrome");
        } else {
            System.out.println("The string \"" + input + "\" is not a palindrome");
        }
    }
}

while (start < end) {

loop until pointers meet or cross to compare characters

if (s.charAt(start) != s.charAt(end)) {

check if characters at pointers differ, means not palindrome

start++;

advance start pointer inward

end--;

move end pointer inward

return true;

all characters matched, confirm palindrome

Output

The string "level" is a palindrome

Complexity Analysis

Time: O(n) because we compare characters from both ends moving inward once

Space: O(1) because only two pointers are used regardless of input size

vs Alternative: Compared to reversing the string and comparing, this uses less space and is faster since no extra string is created

Edge Cases

empty string

returns true because empty string reads the same forwards and backwards

DSA Java

while (start < end) {

single character string

returns true because a single character is always a palindrome

DSA Java

while (start < end) {

string with mixed case

returns false unless cases match exactly; case sensitive

DSA Java

if (s.charAt(start) != s.charAt(end)) {

When to Use This Pattern

When you need to check if a sequence reads the same forwards and backwards, use two pointers from both ends moving inward to compare characters.

Common Mistakes

Mistake: Comparing characters without moving pointers inward, causing infinite loop
Fix: Increment start and decrement end pointers inside the loop after successful comparison

Mistake: Ignoring case differences when palindrome check requires case insensitivity
Fix: Convert string to all lower or upper case before checking

Summary

Checks if a string reads the same forwards and backwards

Use when you want to verify palindrome property efficiently

Compare characters from both ends moving inward until pointers meet or mismatch

Practice

1. What does a palindrome string mean in the context of palindrome detection?

easy

A. A string with all unique characters

B. A string that contains only vowels

C. A string that is sorted alphabetically

D. A string that reads the same forwards and backwards

Solution

1. Step 1: Understand palindrome definition

   A palindrome is a word or phrase that reads the same forwards and backwards.

2. Step 2: Compare options with definition

   Only "a string that reads the same forwards and backwards" matches this definition exactly.

3. Final Answer:

   A string that reads the same forwards and backwards -> Option D

4. Quick Check:

   Palindrome = Same forwards and backwards [OK]

Hint: Palindrome means mirror reading same both ways [OK]

Common Mistakes:

• Confusing palindrome with unique characters
• Thinking palindrome means sorted string
• Assuming palindrome only has vowels

2. Which of the following Java code snippets correctly checks if a string s is a palindrome?

easy

A. for (int i = 0; i < s.length() / 2; i++) { if (s.charAt(i) != s.charAt(s.length() - 1 - i)) return false; } return true;

B. for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != s.charAt(i + 1)) return false; } return true;

C. for (int i = 0; i < s.length() / 2; i++) { if (s.charAt(i) == s.charAt(i + 1)) return false; } return true;

D. for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != s.charAt(s.length() - i)) return false; } return true;

Solution

1. Step 1: Check loop and character comparison logic

   for (int i = 0; i < s.length() / 2; i++) { if (s.charAt(i) != s.charAt(s.length() - 1 - i)) return false; } return true; compares characters from start and end moving towards center correctly.

2. Step 2: Identify errors in other options

   Adjacent chars comparison is incorrect; equality check instead of inequality is wrong; off-by-one index error.

3. Final Answer:

   for (int i = 0; i < s.length() / 2; i++) { if (s.charAt(i) != s.charAt(s.length() - 1 - i)) return false; } return true; -> Option A

4. Quick Check:

   Compare chars from ends moving inward [OK]

Hint: Compare chars from start and end moving inward [OK]

Common Mistakes:

• Using wrong indices causing index out of bounds
• Comparing adjacent characters instead of mirrored ones
• Incorrect loop range causing incomplete checks

3. What will be the output of the following Java code?

String s = "racecar";
boolean isPalindrome = true;
for (int i = 0; i < s.length() / 2; i++) {
    if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
        isPalindrome = false;
        break;
    }
}
System.out.println(isPalindrome);

medium

A. false

B. Compilation error

C. true

D. Runtime exception

Solution

1. Step 1: Analyze the string and loop logic

   String "racecar" is a palindrome. Loop compares mirrored characters correctly.

2. Step 2: Check if any mismatch occurs

   No mismatch found, so isPalindrome remains true and prints true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   "racecar" reads same forwards and backwards [OK]

Hint: Check mirrored chars; no mismatch means true [OK]

Common Mistakes:

• Assuming palindrome check fails for odd length strings
• Confusing loop range causing missed checks
• Misreading output as string instead of boolean

4. Identify the error in the following Java code that attempts to check if a string str is a palindrome:

boolean checkPalindrome(String str) {
    for (int i = 0; i <= str.length() / 2; i++) {
        if (str.charAt(i) != str.charAt(str.length() - i)) {
            return false;
        }
    }
    return true;
}

medium

A. The loop condition should be i < str.length() / 2 instead of <=.

B. The index str.length() - i causes an index out of bounds error.

C. The method should return void instead of boolean.

D. The comparison operator should be == instead of !=.

Solution

1. Step 1: Check index usage in charAt

   Index str.length() - i is off by one; last valid index is str.length() - 1.

2. Step 2: Identify error cause

   Accessing str.charAt(str.length() - i) when i=0 causes index out of bounds.

3. Final Answer:

   Index str.length() - i causes out of bounds error -> Option B

4. Quick Check:

   String indices start at 0, max index = length-1 [OK]

Hint: Check if indices go beyond string length - 1 [OK]

Common Mistakes:

• Using <= in loop causing extra iteration
• Confusing comparison operators
• Wrong return type for boolean method

5. Given a list of strings ["level", "world", "deed", "java", "noon"], which Java code snippet correctly returns a new list containing only the palindromes?

hard

A. List<String> palindromes = list.stream().filter(s -> new StringBuilder(s).reverse().toString().equals(s)).collect(Collectors.toList());

B. List<String> palindromes = list.stream().filter(s -> s.charAt(0) == s.charAt(s.length() - 1)).collect(Collectors.toList());

C. List<String> palindromes = list.stream().filter(s -> s.length() % 2 == 0).collect(Collectors.toList());

D. List<String> palindromes = list.stream().filter(s -> s.equals(s.toUpperCase())).collect(Collectors.toList());

Solution

1. Step 1: Understand palindrome filtering logic

   List<String> palindromes = list.stream().filter(s -> new StringBuilder(s).reverse().toString().equals(s)).collect(Collectors.toList()); reverses string and compares to original, correctly identifying palindromes.

2. Step 2: Analyze other options

   Checking only first and last char equality; filtering even length strings; checking uppercase equality; all incorrect.

3. Final Answer:

   List<String> palindromes = list.stream().filter(s -> new StringBuilder(s).reverse().toString().equals(s)).collect(Collectors.toList()); -> Option A

4. Quick Check:

   Reverse string equals original means palindrome [OK]

Hint: Reverse string and compare to original to find palindrome [OK]

Common Mistakes:

• Checking only first and last characters
• Filtering by string length instead of palindrome
• Confusing uppercase check with palindrome