Palindrome Detection in DSA Java - Execution Trace

Concept Flow - Palindrome Detection

Start with input string

↓

Set left pointer at start

↓

Set right pointer at end

↓

Compare characters at left and right

↓

Move left++ and right--

↓

Left >= Right?

Yes→Palindrome confirmed

No↓

Repeat comparison

Check characters from both ends moving inward; if all pairs match, it's a palindrome.

Execution Sample

DSA Java

String s = "racecar";
int left = 0;
int right = s.length() - 1;
while (left < right) {
  if (s.charAt(left) != s.charAt(right)) return false;
  left++;
  right--;
}
return true;

This code checks if the string 'racecar' reads the same forwards and backwards.

Execution Table

Step	Operation	Left Index	Right Index	Characters Compared	Match?	Action	Visual State
1	Initialize pointers	0	6	r vs r	Yes	Move left++, right--	r a c e c a r
2	Compare characters	1	5	a vs a	Yes	Move left++, right--	r a c e c a r
3	Compare characters	2	4	c vs c	Yes	Move left++, right--	r a c e c a r
4	Check loop condition	3	3	N/A	N/A	Left >= Right, stop	r a c e c a r
5	Result	-	-	-	-	Palindrome confirmed	r a c e c a r

💡 Left pointer reached or passed right pointer, all compared characters matched.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
left	0	1	2	3	3	3
right	6	5	4	3	3	3
match	N/A	true	true	true	N/A	true

Key Moments - 3 Insights

Why do we stop comparing when left pointer is equal to or greater than right pointer?

Because when left >= right, all pairs have been checked. See execution_table row 4 where left and right meet, confirming palindrome.

What happens if characters at left and right do not match?

The function returns false immediately, stopping further checks. This is shown in the 'Match?' column; if 'No', action would be to return false.

Why do we compare characters at left and right indices instead of checking the whole string at once?

Comparing pairs from ends inward is efficient and stops early if mismatch found. This stepwise approach is shown in execution_table rows 1-4.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what are the left and right indices?

A left=2, right=4

B left=3, right=3

C left=1, right=5

D left=0, right=6

💡 Hint

Check the 'Left Index' and 'Right Index' columns in execution_table row 3.

At which step does the algorithm stop comparing characters?

A Step 5

B Step 2

C Step 4

D Step 3

💡 Hint

Look at the 'Action' column where it says 'Left >= Right, stop' in execution_table.

If the character at left=1 was 'b' instead of 'a', what would happen at Step 2?

A Continue to Step 3

B Return false immediately

C Ignore and move pointers

D Restart from beginning

💡 Hint

Refer to 'Match?' and 'Action' columns in execution_table; mismatch causes immediate return false.

Concept Snapshot

Palindrome Detection:
- Use two pointers: left at start, right at end
- Compare characters at left and right
- If mismatch, return false
- Move pointers inward (left++, right--)
- Stop when left >= right
- If all matched, string is palindrome

Full Transcript

Palindrome detection checks if a string reads the same forwards and backwards. We start with two pointers: one at the beginning (left) and one at the end (right) of the string. We compare the characters at these pointers. If they match, we move the left pointer forward and the right pointer backward, then compare again. This continues until the pointers meet or cross. If all compared characters match, the string is a palindrome. If any pair does not match, the check stops immediately and returns false. This method is efficient because it stops early on mismatch and only compares pairs needed.

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