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.

Answer 3

Increment the last character, and if it reaches Z, reset it to A and move to the previous characters. Repeat until you find a character that's not Z. Because Strings are immutable, I suggest using an array of characters instead to avoid allocating lots and lots of new objects.

public static void incrementString(char[] str)
{
    for(int pos = str.length - 1; pos >= 0; pos--)
    {
        if(Character.toUpperCase(str[pos]) != 'Z')
        {
            str[pos]++;
            break;
        }
        else
            str[pos] = 'a';
    }
}

Answer 4

you can use big integer's toString(radix) method like:

import java.math.BigInteger;
public class Strings {
    Strings(final int digits,final int radix) {
        this(digits,radix,BigInteger.ZERO);
    }
    Strings(final int digits,final int radix,final BigInteger number) {
        this.digits=digits;
        this.radix=radix;
        this.number=number;
    }
    void addOne() {
        number=number.add(BigInteger.ONE);
    }
    public String toString() {
        String s=number.toString(radix);
        while(s.length()<digits)
            s='0'+s;
        return s;
    }
    public char convert(final char c) {
        if('0'<=c&&c<='9')
            return (char)('a'+(c-'0'));
        else if('a'<=c&&c<='p')
            return (char)(c+10);
        else throw new RuntimeException("more logic required for radix: "+radix);
    }
    public char convertInverse(final char c) {
        if('a'<=c&&c<='j')
            return (char)('0'+(c-'a'));
        else if('k'<=c&&c<='z')
            return (char)(c-10);
        else throw new RuntimeException("more logic required for radix: "+radix);
    }
    void testFix() {
        for(int i=0;i<radix;i++)
            if(convert(convertInverse((char)('a'+i)))!='a'+i)
                throw new RuntimeException("testFix fails for "+i);
    }
    public String toMyString() {
        String s=toString(),t="";
        for(int i=0;i<s.length();i++)
            t+=convert(s.charAt(i));
        return t;
    }
    public static void main(String[] arguments) {
        Strings strings=new Strings(8,26);
        strings.testFix();
        System.out.println(strings.number.toString()+' '+strings+' '+strings.toMyString());
        for(int i=0;i<Math.pow(strings.radix,3);i++)
            try {
                strings.addOne();
                if(Math.abs(i-i/strings.radix*strings.radix)<2)
                    System.out.println(strings.number.toString()+' '+strings+' '+strings.toMyString());
            } catch(Exception e) {
                System.out.println(""+i+' '+strings+" failed!");
            }
    }
    final int digits,radix;
    BigInteger number;
}

Answer 5

I'd have to agree with @saua's approach if you only wanted the final result, but here is a slight variation on it in the case you want every result.

Note that since there are 26^8 (or 208827064576) different possible strings, I doubt you want them all. That said, my code prints them instead of storing only one in a String Builder. (Not that it really matters, though.)

  public static void base26(int maxLength) {
    buildWord(maxLength, "");
  }
  public static void buildWord(int remaining, String word)
  {
    if (remaining == 0)
    {
      System.out.println(word);
    }
    else
    {
      for (char letter = 'A'; letter <= 'Z'; ++letter)
      {
        buildWord(remaining-1, word + letter);
      }
    }
  }

  public static void main(String[] args)
  {
    base26(8);
  }

Answer 6

I would create a character array and increment the characters individually. Strings are immutable in Java, so each change would create a new spot on the heap resulting in memory growing and growing.

With a character array, you shouldn't have that problem...

Answer 7

Have an array of byte that contain ascii values, and have loop that increments the far right digit while doing carry overs.

Then create the string using

public String(byte[] bytes, String charsetName)

Make sure you pass in the charset as US-ASCII or UTF-8 to be unambiguous.

Answer 8

Just expanding on the examples, as to Implementation, consider putting this into a Class... Each time you call toString of the Class it would return the next value:

public class Permutator {

    private int permutation;

    private int permutations; 

    private StringBuilder stringbuilder;

    public Permutator(final int LETTERS) {

        if (LETTERS < 1) {
            throw new IllegalArgumentException("Usage: Permutator( \"1 or Greater Required\" \)");
        }

        this.permutation = 0;

        // MAGIC NUMBER : 26 = Number of Letters in the English Alphabet 
        this.permutations = (int) Math.pow(26, LETTERS);

        this.stringbuilder = new StringBuilder();

        for (int i = 0; i < LETTERS; ++i) {
            this.stringbuilder.append('a');
        }
    }

    public String getCount() {

        return String.format("Permutation: %s of %s Permutations.", this.permutation, this.permutations);
    }

    public int getPermutation() {

        return this.permutation;
    }

    public int getPermutations() {

        return this.permutations;
    }

    private void permutate() {

        // TODO: Implement Utilising one of the Examples Posted.
    } 

    public String toString() {

        this.permutate();

        return this.stringbuilder.toString();
    }
}    

Answer 9

Building on the solution by @cyberz, the following code is an example of how you could write a recursive call which can be optimized by a compiler that supports Tail Recursion.

The code is written in Groovy, since it runs on the JVM, its syntax closely resembles Java and it's compiler supports tail recursion optimization

static String next(String input) {
    return doNext(input, "")
}

@TailRecursive
@CompileStatic
static String doNext(String input, String result) {
    if(!self) {
        return result
    }

    final String last = input[-1]
    final String nonLast = self.substring(0, input.size()-1)
    if('z' == last) {
        return doNext(nonLast, (nonLast ? 'a' : 'aa') + result)
    }

    return doNext('', nonLast + (((last as Character) + 1) as Character).toString() + result)
}

Answer 10

Since none of the answers were useful to me, I wrote my own code:

/**
 * Increases the given String value by one. Examples (with min 'a' and max 'z'): <p>
 * 
 * - "aaa" -> "aab" <br>
 * - "aab" -> "aac" <br>
 * - "aaz" -> "aba" <br>
 * - "zzz" -> "aaaa" <br>
 * 
 * @param s
 * @param min lowest char (a zero)
 * @param max highest char (e.g. a 9, in a decimal system)
 * @return increased String by 1
 */
public static String incString(String s, char min, char max) {
    char last = s.charAt(s.length() - 1);
    if (++last > max)
        return s.length() > 1 ? incString(s.substring(0, s.length()-1), min, max) + min : "" + min + min;
    else
        return s.substring(0, s.length()-1) + last;
}

Answer 11

public static String incrementString(String string)
{
    if(string.length()==1)
    {
        if(string.equals("z"))
            return "aa";
        else if(string.equals("Z"))
            return "Aa";
        else
            return (char)(string.charAt(0)+1)+"";
    }   
    if(string.charAt(string.length()-1)!='z')
    {
        return string.substring(0, string.length()-1)+(char)(string.charAt(string.length()-1)+1);
    }
    return incrementString(string.substring(0, string.length()-1))+"a";
}

Works for all standard string containing alphabets

Answer 12

I have approach using for loop which is fairly simple to understand. based on [answer]: https://stackoverflow.com/a/2338415/9675605 cyberz answer. This also uses org.apache.commons.lang3.ArrayUtils. to insert letter on first position. you can create your own util for it. If someone finds helpful.

import org.apache.commons.lang3.ArrayUtils;
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 str) {
    boolean increment = true;
    char[] arr = str.toCharArray();
    for (int i = arr.length - 1; i >= 0 && increment; i--) {
      char letter = arr[i];
      if (letter != 'z') {
        letter++;
        increment = false;
      } else {
        letter = 'a';
      }
      arr[i] = letter;
    }
    if (increment) {
      arr = ArrayUtils.insert(0, arr, 'a');
    }
    return new String(arr);
}

Answer 13

It's not much of a "trick", but this works for 4-char strings. Obviously it gets uglier for longer strings, but the idea is the same.

char array[] = new char[4];
for (char c0 = 'a'; c0 <= 'z'; c0++) {
  array[0] = c0;
  for (char c1 = 'a'; c1 <= 'z'; c1++) {
    array[1] = c1;
    for (char c2 = 'a'; c2 <= 'z'; c2++) {
      array[2] = c2;
      for (char c3 = 'a'; c3 <= 'z'; c3++) {
        array[3] = c3;
        String s = new String(array);
        System.out.println(s);
      }
    }
  }
}