Implementing JoinWithAnd method
Regex
I think your String.replaceAll(String, String) is fine, as regular expressions don't fall afoul of any of the rules. :) Just watch out for @Bastien Aracil's comment, that you will be removing literal &quot;null&quot; values.
With that said...
Break the rules...?

DO NOT use arrays
DO NOT use StringBuffer or any other type of optimized String variants

These are going to be nearly impossible to conform, since a String is fundamentally a char array, and even a simple &quot;a&quot; + &quot;b&quot; uses an underlying StringBuilder for the concatenation. If one can partially 'hand-wave' the implicit StringBuilder away when using the + operator, I suppose one can also do a smaller 'hand-wave' of the implicit char array modification with String.concat(String):
private static String join(String first, String second) {
    if (first == null || first.isEmpty()) {
        return second == null ? &quot;&quot; : second;
    }
    return second == null ? first : first.concat(&quot; AND &quot;).concat(second);
}

What we do here is to codify our logic as such:

If the first string is either null or empty, we either return second or an empty one.
Afterwards, if the second string is null, we return first, i.e. no concatenation done, or actually perform the concatenation with &quot; AND &quot;.

We then just need to 'recursively' call this with the five arguments, and a null or &quot;&quot; as a 'starter' with a:
private static String joinWithAnd(String a, String b, String c, String d, String e) {
    return join(join(join(join(join(null, a), b), c), d), e);
}

Java 8
Going further, we can just rely on streams (not collections) and StringJoiner (technically not a String 'variant', whatever that means) to get the same output:
private static String joinWithAnd(String a, String b, String c, String d, String e) {
    return Stream.of(a, b, c, d, e)
                .filter(Objects::nonNull)
                .collect(Collectors.joining(&quot; AND &quot;));
}

And, if one is being extra pedantic with the question's language, we can replace Stream.of(T...), technically an array, with multiple Stream.concat(Stream, Stream) calls:
// return Stream.of(a, b, c, d, e)
return Stream.concat(Stream.concat(Stream.concat(Stream.concat(
                Stream.of(a), Stream.of(b)), Stream.of(c)), Stream.of(d)), Stream.of(e))