confused how this palindrome test works

Question

This code works for testing a simple palindrome, but I'm confused as to how it works. I'm confused with the while loop condition, checking if (left < right) and how that automatically means it is not a palindrome.

left = 0;
right = i.length() -1;

while(i.charAt(left) == i.charAt(right) && right > left){
    left++;
    right--;
}

System.out.println();
if (left < right)
    System.out.println ("That string is Not a palindrome.");
else
    System.out.println("That string IS a palindrome");

Answer 1

It helps to use print statements to watch what the program is doing as it runs.

class Ideone
{
    private static void checkPalindrome(String i) {
        int left = 0;
        int right = i.length() -1;
        System.out.println("This word is: " + i);
        System.out.println("Checking charAt(" + left + ") which is " +
            i.charAt(left) + " and chartAt(" + right + ") which is " +
            i.charAt(right));
        while(i.charAt(left) == i.charAt(right) && right > left) {
            left++; right--;
            System.out.println("Checking charAt(" + left + ") which is " +
                i.charAt(left) + " and chartAt(" + right + ") which is " +
                i.charAt(right));
        }

        System.out.println();
        if (left < right)
            System.out.println ("That string is Not a palindrome.");
        else
            System.out.println("That string IS a palindrome");
        System.out.println();
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        checkPalindrome("racecar");
        checkPalindrome("abba");
        checkPalindrome("java");
    }
}

Output

This word is: racecar
Checking charAt(0) which is r and chartAt(6) which is r
Checking charAt(1) which is a and chartAt(5) which is a
Checking charAt(2) which is c and chartAt(4) which is c
Checking charAt(3) which is e and chartAt(3) which is e

That string IS a palindrome

This word is: abba
Checking charAt(0) which is a and chartAt(3) which is a
Checking charAt(1) which is b and chartAt(2) which is b
Checking charAt(2) which is b and chartAt(1) which is b

That string IS a palindrome

This word is: java
Checking charAt(0) which is j and chartAt(3) which is a

That string is Not a palindrome.

As you can see, the while loop starts from the far ends of the string and compares the characters on each side; if they are the same, it moves in one character on each side. It checks for right > left so that it knows when to stop. Once it reaches the middle, right will be at least equal, if not greater than, left since they have met in the middle and are going opposite directions.

The boolean negation of left < right is equivalent to left >= right. This'll be true if the two met in the middle. If left < right then they failed to meet in the middle. You should be able to see this in the above output.

Run this code on ideone and play with it some more.

Answer 2

The while loop basically walks over the potential palindrome starting on opposite sides simultaneously, and compares the characters on each side. It's checking if (right > left) since if it is, it means that the 'right' and 'left' counters didn't passed by each other, therefor didn't reach (or passed) the middle of the string. After this check, it decrements right (so it would get a bit closer to the center of the string) and increments 'left' (for the same reason).

At the end, if 'left' is still less than 'right', it means that the loop stopped before 'left' or 'right' got to the middle of the string, and that happened since the condition that the characters on opposite indexes would match was false at some stage.

If they did get to (or passed) the middle, 'left' will be >= 'right' and it means that the character matching condition was true at least to the middle of the string, hence, a palindrome.

Answer 3

The Palindrome test will only work if your string is all upper case or lower case.

The while loop will end when either the left character does not equal the right character, or the right index > the left index (you have passed the "middle" of the string.

if (left < right) that is the same as right > left and the string is a palindrome (of one case), otherwise the left character did not equal the right character.

I hope that is helpful.

Answer 4

Condition in while statement checks if X == Y and X < Y. It breaks of out of while loop if those conditions are not valid anymore.

Consider below palindrome.

Iteration 1:

    X                                 Y
    +                                 +
    |                                 |
  +-v--+----+---+---+---+---+---+---+-v-+
  |    |    |   |   |   |   |   |   |   |
  | A  | B  | C | D | E | D | C | B | A |
  +----+----+---+---+---+---+---+---+---+

Iteration 2:

  +----+----+---+---+---+---+---+---+---+
  |    |    |   |   |   |   |   |   |   |
  | A  | B  | C | D | E | D | C | B | A |
  |    |    |   |   |   |   |   |   |   |
  +----+----+---+---+---+---+---+---+---+
         ^                        ^
         |                        |
         +                        +

         X                        Y

Iteration 3:

              X               Y
              +               +
              |               |
              v               v
  +----+----+---+---+---+---+---+---+---+
  |    |    |   |   |   |   |   |   |   |
  | A  | B  | C | D | E | D | C | B | A |
  |    |    |   |   |   |   |   |   |   |
  +----+----+---+---+---+---+---+---+---+

Iteration 4:

                  X       Y
                  +       +
                  |       |
  +- --+----+---+-v-+---+-v-+---+---+- -+
  |    |    |   |   |   |   |   |   |   |
  | A  | B  | C | D | E | D | C | B | A |
  +----+----+---+---+---+---+---+---+---+

Iteration 5: Loop would break at this point. Since X < Y is not valid anymore

                     XY
                     ++
                     ||
  +----+----+---+---+vv-+---+---+---+---+
  |    |    |   |   |   |   |   |   |   |
  | A  | B  | C | D | E | D | C | B | A |
  |    |    |   |   |   |   |   |   |   |
  +----+----+---+---+---+---+---+---+---+

If above example was not a palindrome and looks something like this

  +- --+----+---+-v-+---+-v-+---+---+- -+
  |    |    |   |   |   |   |   |   |   |
  | A  | B  | K | D | E | D | C | B | A |
  +----+----+---+---+---+---+---+---+---+

Then your while loop breaks at 3rd Iteration since you first condition X==Y won't be valid. At this point X will still be Less than Y. So if a string is not a palindrome while loop will surely break before both X & Y meet i.e. always X < Y