Link shortener application - return the "following" string
Consider wrapping getFirst() into getNext(String) - just have it return "A" if it takes in a null or empty string. That might make it a little easier for the client to use.
getFirst(int) can leverage Arrays.fill(), which will make it a little easier to read. Consider throwing an exception if the minLength is less than zero - otherwise you get an empty string returned. Another option would be to return "A". 
The core problem can be solved non-recursively. A helper method to return the next character would be, well, helpful, and easier to read than what you're doing now. The math gets done inside the loop, and you prepend an 'A' if appropriate.
You might want to make 'A' a constant, since it's special.


If you make the changes I suggest, your code might look something like:

import java.util.Arrays;
import java.util.regex.Pattern;

public class ProceduralStringCreator {

    private static final Pattern VALID = Pattern.compile("[a-zA-Z0-9]+");
    private static final char FIRST_CHARACTER = 'A';

    public static String next(final int size) {
        if (size &lt; 0) {
            throw new IllegalArgumentException("Size must be greater than or equal to zero, was " + size);
        }
        final char[] value = new char[size];
        Arrays.fill(value, FIRST_CHARACTER);
        return new String(value);
    }

    public static String next(final String current) throws BadFormatException {
        if (current == null || current.isEmpty()) {
            return Character.toString(FIRST_CHARACTER);
        }

        if (!VALID.matcher(current).matches()) {
            throw new BadFormatException("String contains illegal characters.");
        }

        final StringBuilder stringBuilder = new StringBuilder(current);
        int index = stringBuilder.length();

        do {
            index--;
            stringBuilder.setCharAt(index, nextCharacter(stringBuilder.charAt(index)));
        } while ((index &gt;= 1) &amp;&amp; (stringBuilder.charAt(index) == FIRST_CHARACTER));

        if ((index == 0) &amp;&amp; (stringBuilder.charAt(index) == FIRST_CHARACTER)) {
            stringBuilder.insert(0, FIRST_CHARACTER);
        }

        return stringBuilder.toString();
    }

    private static char nextCharacter(final char character) {
        switch (character) {
        case 'Z':
            return 'a';
        case 'z':
            return '0';
        case '9':
            return 'A';
        default :
            return (char) (character + 1);
        }
    }

}