The Next Palindrome

I recently came across a challenging problem on SPOJ called The Next Palindrome. It involves finding the next palindrome given a very large integer (with more than 1000000 digits). For example, the next palindrome after 2133 is 2222.

A palindrome is any string which reads the same when read from left-to-right and right-to-left, for example, 818. Here is a method which tests if a string is a palindrome:

private static boolean isPalindrome(String s) {
  for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
    if (s.charAt(i) != s.charAt(j)) {
      return false;
    }
  }
  return true;
}

The obvious way to solve the next palindrome problem is by brute-force i.e. keep incrementing the integer until you hit a palindrome.

public static String bruteForce(String s){
  BigInteger i = new BigInteger(s) ;
  while(true){
    i = i.add(BigInteger.ONE);
    final String result = i.toString();
    if(isPalindrome(result)){
      return result;
    }
  }
}

This approach is VERY slow for large numbers! A faster way is "mirroring" the number about its centre. For example, the mirror of 65432 is 65456, which is the next palindrome. The following method mirrors a string:

public static String mirror(String s) {
  final char[] arr = s.toCharArray();
  int midpoint = arr.length / 2;
  int i=arr.length%2==0?midpoint:midpoint+1;
  while (i < arr.length) {
    arr[i] = arr[midpoint - 1];
    i++;
    midpoint--;
  }
  return new String(arr);
}

BUT sometimes a mirrored number might be smaller than the original. For example, the mirror of 12345 is 12321, which is smaller. In this case, we need to increment the original number from the middle and then mirror it. So when 12345 is incremented from the middle, you get 12445 which mirrors to 12421, the next palindrome. Incrementing from the middle can get tricky if there is a 9 in the middle. For example, 12945 increments to 13045 which then mirrors to 13031. The following method increments a number from the middle:

public static String incrementFromMiddle(String s) {
  final char[] arr = s.toCharArray();
  final int midpoint = arr.length / 2;
  int currPoint=arr.length%2==0?midpoint-1:midpoint;
  boolean found = false;

  while (currPoint >= 0 && !found) {
    char c = arr[currPoint];
    char inc;
    if (c == '9') {
      inc = '0';
    }
    else {
      inc = (char) (c + 1);
      found = true;
    }
    arr[currPoint] = inc;
    if (!found) {
      currPoint--;
    }
  }

  if (!found) {
    // we have fallen off the start of the string
    // example 999 has become 009. Add a one on to give: 1009
    final char[] newarr = new char[arr.length + 1];
    newarr[0] = '1';
    System.arraycopy(arr, 0, newarr, 1, arr.length);
    return new String(newarr);
  }
  else {
    return new String(arr);
  }
}

Complete Code Listing:
That's it! Here is the complete java program to find the next palindrome: (Also available here)

import java.io.BufferedOutputStream;
import java.io.FileDescriptor;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.math.BigInteger;
import java.util.Scanner;

/**
 * Finds the Next Palindrome.
 */
public class Main {

  /**
   * Brute Force method.
   * Keeps incrementing by one until a palindrome is found.
   * @param s
   * @return the next palindrome
   */
  public static String bruteForce(String s){
    BigInteger i = new BigInteger(s) ;
    while(true){
      i = i.add(BigInteger.ONE);
      final String result = i.toString();
      if(isPalindrome(result)){
        return result;
      }
    }
  }

  /**
   * Mirrors a string around the centre.
   * Example: abc -> aba and abcd -> abba
   * @param s
   * @return mirrored string
   */
  public static String mirror(String s) {
    final char[] arr = s.toCharArray();
    int midpoint = arr.length / 2;
    int i = arr.length % 2 == 0 ? midpoint : midpoint + 1;
    while (i < arr.length) {
      arr[i] = arr[midpoint - 1];
      i++;
      midpoint--;
    }
    return new String(arr);
  }

  /**
   * Increments the middle digit.
   * Example: 12345 -> 12445 and 1234 -> 1334
   * 9s get incremented to 0 and carried over.
   * Example: 12945 -> 13045
   * @param s
   * @return incremented string
   */
  public static String incrementFromMiddle(String s) {

    final char[] arr = s.toCharArray();
    final int midpoint = arr.length / 2;
    int currPoint = arr.length % 2 == 0 ? midpoint - 1 : midpoint;
    boolean found = false;

    while (currPoint >= 0 && !found) {
      char c = arr[currPoint];
      char inc;
      if (c == '9') {
        inc = '0';
      }
      else {
        inc = (char) (c + 1);
        found = true;
      }
      arr[currPoint] = inc;
      if (!found) {
        currPoint--;
      }
    }

    if (!found) {
      // we have fallen off the start of the string
      // example 999 has become 009. Add a one on to give: 1009
      final char[] newarr = new char[arr.length + 1];
      newarr[0] = '1';
      System.arraycopy(arr, 0, newarr, 1, arr.length);
      return new String(newarr);
    }
    else {
      return new String(arr);
    }
  }



  /**
   * Next Palindrome using the mirroring approach.
   * @param s
   * @return
   */
  public static String getNextPalindrome(String s) {
    String mirrored = mirror(s);

    //the mirror might be smaller than original, so increment it and try again.
    if (compare(mirrored, s) <= 0) {
      mirrored = mirror(incrementFromMiddle(s));
    }
    return mirrored;
  }

  /**
   * @param s
   * @return true if the specified string is a palindrome.
   */
  private static boolean isPalindrome(String s) {
    //compare first and last chars, and so on...
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
      if (s.charAt(i) != s.charAt(j)) {
        return false;
      }
    }
    return true;
  }

  /**
   * Compares two numerical mirrored strings.
   * Assumes they have the same length.
   * Only compares the second half of the strings.
   * @param s
   * @param t
   * @return -1, 0 or 1 if s<t, s==t or s>t
   */
  private static int compare(String s, String t){
    //only check second half
    final int midpoint = s.length() / 2;
    int i = s.length() % 2 == 0 ? midpoint : midpoint + 1;
    for (; i < s.length(); i++) {
      if(s.charAt(i) < t.charAt(i)){
        return -1 ;
      }
      else if (s.charAt(i) > t.charAt(i)){
        return 1;
      }
    }
    return 0;
  }

  /**
   * The main method.
   *
   * @param args
   */
  public static void main(String[] args) {
    // fast output as there is no flush on \n
    final FileOutputStream fdout =
         new FileOutputStream(FileDescriptor.out);
    final BufferedOutputStream bos =
         new BufferedOutputStream(fdout, 1024);
    final PrintStream ps = new PrintStream(bos, false);
    System.setOut(ps);

    try {
      final Scanner scanner = new Scanner(System.in);
      scanner.next();
      while (scanner.hasNext()) {
        final String s = scanner.next();
        System.out.println(getNextPalindrome(s));
      }
    }
    catch (Exception e) {
      e.printStackTrace();
    }
    finally {
      ps.close();
    }
  }
}

Links:
SPOJ PALIN: Next Palindrome