Palindrome Check II in JavaScript with O(n) Time Complexity

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

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

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 related to DNA sequencing.

Common pitfalls include not considering spaces, punctuation, or case sensitivity. For simplicity, we assume the input string is case-sensitive and includes spaces.

Approach

To solve this problem, we can use a two-pointer technique:

• Initialize one pointer at the start of the string and another at the end.
• Compare the characters at these pointers.
• If they are equal, move the start pointer forward and the end pointer backward.
• If they are not equal, the string is not a palindrome.
• Continue this process until the pointers meet or cross each other.

This approach ensures we only traverse the string once, achieving O(n) time complexity with O(1) extra space.

Algorithm

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

Code Implementation

/**
 * Function to check if a given string is a palindrome
 * @param {string} s - The input string
 * @return {boolean} - True if the string is a palindrome, false otherwise
 */
function isPalindrome(s) {
    // Initialize two pointers
    let i = 0;
    let j = s.length - 1;

    // Loop until the pointers meet
    while (i < j) {
        // If characters at pointers do not match, return false
        if (s[i] !== s[j]) {
            return false;
        }
        // Move the pointers
        i++;
        j--;
    }

    // If all characters matched, return true
    return true;
}

// Example usage:
console.log(isPalindrome("madam racecar madam")); // Output: true
console.log(isPalindrome("abcbx")); // Output: false

Complexity Analysis

The time complexity of this approach 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

Consider the following edge cases:

• Empty string: Should return true.
• Single character string: Should return true.
• Strings with spaces and punctuation: Depending on the problem constraints, these may need to be handled.

Examples:

isPalindrome("") // true
isPalindrome("a") // true
isPalindrome("A man, a plan, a canal, Panama") // false (case-sensitive and includes spaces)

Testing

To test the solution comprehensively, consider using a variety of test cases:

• Simple palindromes: "madam", "racecar"
• Non-palindromes: "hello", "world"
• Edge cases: "", "a", "ab"

Using a testing framework like Jest can help automate and manage these tests.

Thinking and Problem-Solving Tips

When approaching such problems:

• Understand the problem requirements and constraints.
• Break down the problem into smaller, manageable parts.
• Consider different approaches and their trade-offs.
• Practice similar problems to improve problem-solving skills.

Conclusion

Understanding and solving palindrome problems is crucial for developing strong problem-solving skills. This problem teaches the importance of efficient algorithms and space optimization. Practice and exploration of similar problems can further enhance these skills.

Additional Resources

For further reading and practice:

• LeetCode: Valid Palindrome
• GeeksforGeeks: Check if a string is a palindrome
• HackerRank: Palindrome Index