Solution: Valid Palindrome

Let's solve the Valid Palindrome problem using the Two Pointers pattern.

We'll cover the following

Statement

Write a function that takes a string, s, as an input and determines whether or not it is a palindrome.

Note: A palindrome is a word, phrase, or sequence of characters that reads the same backward as forward.

Constraints:

  • 1≤1 \leq s.length ≤2×105\leq 2 \times 10^5
  • The string s will not contain any white space and will only consist of ASCII characters(digits and letters).

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach to solve this problem is to reverse the string and then compare the reversed string with the original string. If they match, the original string is a valid palindrome. Although this solution has a linear time complexity, it requires extra space to store the reversed string, making it less efficient in terms of space complexity. Therefore, we can use an optimized approach to save extra space.

Optimized approach using two pointers

A palindrome is a word or phrase that reads the same way when it is reversed. This means the characters at both ends of the word or phrase should be the same.

The essence of this solution is the efficient use of two pointers converging from opposite ends toward the middle of the string. One pointer begins from the start and moves forward, while the other starts from the end and moves backward in the string. As they converge toward each other, they compare characters at each step to identify any mismatch. The string is a palindrome if these pointers converge in the middle without discovering mismatching characters.

This two pointers approach would allow us to solve this problem in linear time without any additional space complexity or the use of built-in functions. This is because we’ll traverse the array from the start and the end simultaneously to reach the middle of the string.

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

We’ll have two pointers, where the first pointer is at the starting element of our string, while the second pointer is at the end of the string. We move the two pointers towards the middle of the string and, at each iteration, we compare each element. The moment we encounter a nonidentical pair, we can return FALSE because our string can’t be a palindrome.

We will construct the solution step by step and the first step is to set up two pointers and move them toward the middle of the string. We can do that with the following code snippet:

class ValidPalindrome {
  public static String isPalindrome(String s) {
    System.out.println("String to check: " + s + ". Length of string: " + s.length());
    int left = 0;
    int right = s.length() - 1;
    int i = 1;
    // The terminating condition for the loop is when both the pointers reach the same element or when they cross each other.
    while (left < right) {
      System.out.println("In iteration " + i + ", left = " + left + ", right = " + right);
      System.out.println("The current element being pointed to by the left pointer is '" + s.charAt(left) + "'");
      System.out.println("The current element being pointed to by the right pointer is '" + s.charAt(right) + "'");
      left = left + 1; // Heading towards the right
      right = right - 1; // Heading towards the left
      i = i + 1;
      System.out.println(new String(new char[100]).replace('\0', '-'));
    }
    System.out.println("Loop terminated with left = " + left + ", right = " + right);
    return "The pointers have either reached the same index, or have crossed each other, hence we don't need to look further.";
  }
  //Driver code
  public static void main(String[] arg) {
    String[] testCase = {
      "RACECAR",
      "ABBA",
      "TART"
    };
    for (int k = 0; k < testCase.length; k++) {
      System.out.println("Test Case # " + (k + 1));
      System.out.println(isPalindrome(testCase[k]));
      System.out.println(new String(new char[100]).replace('\0', '-'));
    }
  }
}
Valid Palindrome

That's how we always traverse in opposite directions with the help of two pointers. The termination condition for our code is that the left pointer should always be less than the right pointer, because the moment they cross each other, we reach the middle of the string and don't need to go any further. We can check how this works with our example.

In the code sample above, we see that in the case of the palindromic strings, at each step in the traversal toward the middle of the string, the characters at both the left and the right indexes are identical. However, with the third test case, “TART” (which isn't a palindromic string), in the second iteration of the loop, we see that our output identifies that the characters at the left and right indexes aren't the same. This observation allows us to add a simple check to our code.

If we encounter a nonidentical pair, we can simply return FALSE, because the string isn't a palindrome, and we don't need to test any further. Otherwise, we're able to traverse to the middle of the string. In this case, we return TRUE, because each element has a match at the expected position in the string.

class ValidPalindrome {
  public static boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    System.out.println("The element being pointed to by the left pointer is '" + s.charAt(left) + "'");
    System.out.println("The element being pointed to by the right pointer is '" + s.charAt(right) + "'");
    while (left < right) {
      System.out.println("We check if the two elements are indeed the same, in this case...");
      if (s.charAt(left) != s.charAt(right)) // If the elements at index left and index right are not equal,
      {
        System.out.println("The elements aren't the same, hence we return False");
        return false; // then the symmetry is broken, the string is not a palindrome
      }
      System.out.println("They are the same, thus we move the two pointers toward the middle to continue the \nverification process.\n");
      left = left + 1; // Heading towards the right
      right = right - 1; // Heading towards the left
      System.out.println("The new element at the left pointer is " + s.charAt(left));
      System.out.println("The new element at the right pointer is " + s.charAt(right));
    }
    // We reached the middle of the string without finding a mismatch, so it is a palindrome.
    return true;
  }
  
  //Driver code
  public static void main(String[] arg) {
    String[] testCase = {
      "RACEACAR",
      "A",
      "ABCDEFGFEDCBA",
      "ABC",
      "ABCBA",
      "ABBA",
      "RACEACAR"
    };
    for (int k = 0; k < testCase.length; k++) {
      System.out.println("Test Case #" + (k + 1));
      System.out.println(new String(new char[100]).replace('\0', '-'));
      System.out.println("The input string is " + testCase[k] + "' and the length of the string is " + testCase[k].length() + ".");
      System.out.println("\nIs it a palindrome?..... " + isPalindrome(testCase[k]));
      System.out.println(new String(new char[100]).replace('\0', '-'));
    }
  }
}
Valid Palindrome

Just the code

Here’s the complete solution to this problem:

class ValidPalindrome {
  public static 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 = left + 1;
      right = right - 1;
    }
    return true;
  }
  
  //Driver code
  public static void main(String[] arg) {
    String[] testCase = {
      "RACEACAR",
      "A",
      "ABCDEFGFEDCBA",
      "ABC",
      "ABCBA",
      "ABBA",
      "RACEACAR"
    };
    for (int k = 0; k < testCase.length; k++) {
      System.out.println("Test Case #" + (k + 1));
      System.out.println(new String(new char[100]).replace('\0', '-'));
      System.out.println("The input string is " + testCase[k] + "' and the length of the string is " + testCase[k].length() + ".");
      System.out.println("\nIs it a palindrome?..... " + isPalindrome(testCase[k]));
      System.out.println(new String(new char[100]).replace('\0', '-'));
    }
  }
}
Valid Palindrome

Solution summary

  • Initialize two pointers and move them from opposite ends.
  • The first pointer starts at the beginning of the string and moves toward the middle, while the second pointer starts at the end and moves toward the middle.
  • Compare the elements at each position to detect a nonmatching pair.
  • If both pointers reach the middle of the string without encountering a nonmatching pair, the string is a palindrome.

Time complexity

The time complexity is O(n)O(n), where nn is the number of characters in the string. However, our algorithm will only run (n/2)(n/2) times, since two pointers are traversing toward each other.

Space complexity

The space complexity is O(1)O(1), since we use constant space to store two indexes.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.