Palindrome Detection in DSA Java - Time & Space Complexity

Time Complexity: Palindrome Detection

O(n)

Understanding Time Complexity

We want to know how the time to check if a word or phrase is a palindrome changes as the input gets longer.

How does the number of steps grow when the input size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public boolean isPalindrome(String s) {
    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 a string reads the same forwards and backwards by comparing characters from both ends moving towards the center.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing characters at positions from start and end of the string.
• How many times: Up to half the length of the string (n/2 times).

How Execution Grows With Input

As the string gets longer, the number of character comparisons grows roughly half as fast.

Input Size (n)	Approx. Operations
10	5 comparisons
100	50 comparisons
1000	500 comparisons

Pattern observation: The number of steps grows linearly with input size, but only half as many comparisons are needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to check a palindrome grows in a straight line as the input gets longer.

Common Mistake

[X] Wrong: "Checking a palindrome takes time proportional to the square of the string length because of nested checks."

[OK] Correct: The code only compares pairs of characters once, moving inward, so it does not repeat work inside nested loops.

Interview Connect

Understanding this linear time check helps you explain efficient string processing, a common skill interviewers look for.

Self-Check

"What if we ignored case and spaces when checking the palindrome? How would the time complexity change?"

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