Start learning free

LESSON 244 OF 410 · TWO POINTERS

Palindrome Check in O(n) Time Complexity using JavaScript

Practice O(n) Read the full explanation

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 (the two-pointer approach below achieves this).


Hints:

For the string to be a palindrome, for each character, there is a corresponding element which should be equal to that one:
  • the character at index 0 equals the character at index n - 1
  • the character at index 1 equals the character at index n - 2
  • the character at index 2 equals the character at index 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 through the algorithm?

For as long as i < j:
  • 1. We should check if the characters at indices i and j are different, 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.

STEP 1 OF 6
    Ctrl + Enter to check

    JAVASCRIPT · TWO POINTERS

    Palindrome Check in JavaScript, explained

    Problem Definition

    The problem requires us to determine if a given string is a palindrome. A palindrome is a sequence of characters that reads the same backward as forward.

    Input: A string s.

    Output: A boolean value true if the string is a palindrome, otherwise false.

    Constraints:

    • The algorithm should run in O(n) time complexity.
    • The algorithm should use O(1) extra space.

    Example:

    Input:  "madam racecar madam"
Output: true
    Input:  "abcbx"
Output: false

    Understanding the Problem

    The core challenge is to check if the string reads the same backward as forward. This problem is significant in various applications such as text processing, data validation, and more. A common pitfall is to overlook the need for an efficient solution that runs in linear time and uses constant space.

    Approach

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

    1. Initialize two pointers, one at the beginning and one at the end of the string.
    2. Compare the characters at these pointers.
    3. If the characters are not equal, return false.
    4. Move the pointers towards the center of the string.
    5. If all characters match, return true.

    This approach ensures that we only traverse the string once, achieving O(n) time complexity, and we use only a few extra variables, achieving O(1) space complexity.

    Algorithm

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

    1. Initialize two pointers, i at the start (0) and j at the end (n-1) of the string.
    2. While i is less than j:
      • Check if s[i] is not equal to 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} - Returns true if the string is a palindrome, otherwise false.
 */
function isPalindrome(s) {
    // Initialize two pointers
    let i = 0;
    let j = s.length - 1;

    // Loop until the pointers meet in the middle
    while (i < j) {
        // If characters at the pointers do not match, return false
        if (s[i] !== s[j]) {
            return false;
        }
        // Move the pointers towards the center
        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

    Time Complexity: O(n), where n is the length of the string. We traverse the string once.

    Space Complexity: O(1), as we use only a few extra variables.

    Edge Cases

    Consider the following edge cases:

    • Empty string: Should return true.
    • Single character string: Should return true.
    • Strings with special characters and spaces: Ensure the algorithm handles them correctly.
    Input:  ""
Output: true
    Input:  "a"
Output: true

    Testing

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

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

    Use testing frameworks like Jest or Mocha 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 optimize it.
    • Practice similar problems to improve problem-solving skills.

    Conclusion

    In this blog post, we discussed how to determine if a string is a palindrome using a two-pointer technique. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving algorithmic thinking and coding skills.

    Additional Resources

    For further reading and practice:

    Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free