Palindrome Check in Java

Given a string, determine if it is a palindrome.

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward

Example 1:

Input:  "madam racecar madam"

Output: true

Example 2:

Input:  "abcbx"

Output: false

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

Hints:

For the string to be a palindrome, for each character, there is a corresponding element which should be equal to that one:

s[0] == s[n - 1]
s[1] == s[n - 2]
s[2] == s[n - 3]
...

How can we check all these pairs of corresponding characters while traversing the string one time?

We can use two pointers! One index variable i starting from the beginning (i = 0) and one index variable j starting from the end of the string (j = n - 1). How should we move these pointers throught the algorithm?

For as long as i < j:

1. We should check if s[i] != s[j] and if so, we conclude the string is not a palindrome and return false.
2. Move i one step to the right.
3. Move j one step to the left.
4. Go to step 1.

If i became greater than or equal to j and we haven't returned false, then we can conclude the string is a palindrome and return true.

Understanding the Problem

The core challenge of this problem is to determine if a given string reads the same backward as forward. This is significant in various applications such as text processing, data validation, and even in some algorithms where symmetry is a key factor. A common pitfall is to overlook the need for an efficient solution that runs in O(n) time and uses O(1) extra space.

Approach

To solve this problem, we can use a two-pointer technique. One pointer starts at the beginning of the string, and the other starts at the end. We compare the characters at these pointers and move them towards the center. If all corresponding characters are equal, the string is a palindrome.

Naive Solution

A naive solution would be to reverse the string and compare it with the original. However, this approach uses O(n) extra space for the reversed string, which is not optimal.

Optimized Solution

The optimized solution uses the two-pointer technique, which only requires O(1) extra space and runs in O(n) time. This is more efficient and meets the problem's constraints.

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

Initialize two pointers, i at the start (0) and j at the end (n-1) of the string.
While i < j:
- Check if s[i] != s[j]. If true, return false.
- Increment i and decrement j.
If the loop completes without returning false, return true.

Code Implementation

public class PalindromeCheck {
    public static boolean isPalindrome(String s) {
        // Initialize two pointers
        int i = 0;
        int j = s.length() - 1;
        
        // Loop until the pointers meet in the middle
        while (i < j) {
            // Check if characters at i and j are not equal
            if (s.charAt(i) != s.charAt(j)) {
                return false; // Not a palindrome
            }
            // Move the pointers
            i++;
            j--;
        }
        
        // If we complete the loop, the string is a palindrome
        return true;
    }

    public static void main(String[] args) {
        // Test cases
        System.out.println(isPalindrome("madam racecar madam")); // true
        System.out.println(isPalindrome("abcbx")); // false
    }
}

Complexity Analysis

The time complexity of this algorithm is O(n) because we traverse the string once. The space complexity is O(1) as we only use a constant amount of extra space for the pointers.

Edge Cases

Potential edge cases include:

Empty string: Should return true.
Single character string: Should return true.
Strings with special characters or spaces: Should be handled correctly.

Examples:

Input: ""
Output: true

Input: "a"
Output: true

Input: "A man, a plan, a canal, Panama"
Output: true (if spaces and punctuation are ignored)

Testing

To test the solution comprehensively, include a variety of test cases:

Simple palindromes: "madam", "racecar"
Non-palindromes: "hello", "world"
Edge cases: "", "a", "A man, a plan, a canal, Panama"

Use a testing framework like JUnit for automated testing.

Thinking and Problem-Solving Tips

When approaching such problems:

Understand the problem requirements and constraints.
Think about different approaches and their trade-offs.
Start with a simple solution and then optimize it.
Practice similar problems to improve problem-solving skills.

Conclusion

Understanding and solving palindrome problems is crucial for developing efficient algorithms. The two-pointer technique is a powerful tool for such problems, providing an optimal solution in terms of time and space complexity. Practice and exploration of similar problems will further enhance your skills.

Additional Resources

For further reading and practice:

Palindrome Check in Java with O(n) Time Complexity