I was asked about immutable strings in Java. I was tasked with writing a function that concatenated a number of "a"s to a string.

What I wrote:

public String foo(int n) {
    String s = "";
    for (int i = 0; i < n; i++) {
        s = s + "a"
    }
    return s;
}

I was then asked how many strings this program would generate, assuming garbage collection does not happen. My thoughts for n=3 was

1. ""
2. "a"
3. "a"
4. "aa"
5. "a"
6. "aaa"
7. "a"

Essentially 2 strings are created in each iteration of the loop. However, the answer was n². What strings will be created in memory by this function and why is that way?