How to increment a java String through all the possibilities?

Question

I need to increment a String in java from "aaaaaaaa" to "aaaaaab" to "aaaaaac" up through the alphabet, then eventually to "aaaaaaba" to "aaaaaabb" etc. etc.

Is there a trick for this?

Answer 1

You're basically implementing a Base 26 number system with leading "zeroes" ("a").

You do it the same way you convert a int to a base-2 or base-10 String, but instead of using 2 or 10, you use 26 and instead of '0' as your base, you use 'a'.

In Java you can easily use this:

public static String base26(int num) {
  if (num < 0) {
    throw new IllegalArgumentException("Only positive numbers are supported");
  }
  StringBuilder s = new StringBuilder("aaaaaaa");
  for (int pos = 6; pos >= 0 && num > 0 ; pos--) {
    char digit = (char) ('a' + num % 26);
    s.setCharAt(pos, digit);
    num = num / 26;
  }
  return s.toString();
}

The basic idea then is to not store the String, but just some counter (int an int or a long, depending on your requirements) and to convert it to the String as needed. This way you can easily increase/decrease/modify your counter without having to parse and re-create the String.

Answer 2

The following code uses a recursive approach to get the next string (let's say, from "aaaa" to "aaab" and so on) without the need of producing all the previous combinations, so it's rather fast and it's not limited to a given maximum string length.

public class StringInc {
 public static void main(String[] args) {
   System.out.println(next("aaa")); // Prints aab

   System.out.println(next("abcdzz")); // Prints abceaa

   System.out.println(next("zzz")); // Prints aaaa
 }

 public static String next(String s) {
   int length = s.length();
   char c = s.charAt(length - 1);

   if(c == 'z')
     return length > 1 ? next(s.substring(0, length - 1)) + 'a' : "aa";

   return s.substring(0, length - 1) + ++c;
 }
}

As some folks pointed out, this is tail recursive, so you can reformulate it replacing the recursion with a loop.