Concatenation using string builder

String s1 = "hello ";
String s2 = "world";
String s3 = s1+s2;

It may surprise you that the above operation is an O(n) process. This is because the process of 'adding two strings' is actually copying each character into a new array.

// this process takes O(s1.length() + s2.length()) or O(max(s1.length(),s2.length()))
public String concatenate(String s1, String s2){
	// some operation to create a buffer of a size s1.length() + s2.length()
    // copy each character of s1 and s2 into the buffer
    // return
}

What if you wanted to concatenate n words of fixed length k? Then it would look something like this:

public String concatenateManyStrings(String[] strings){
	String result = "";
    for(String s: strings){
    	result = concatenate(result, s);
    }
}

What's the efficiency of this concatenation?

Well, we can make a table:

iteration	number of constant time operations for THIS iteration
1	0+k = k
2	k+k = 2k
3	2k + k = 3k
4	3k + k = 4k
5	4k + k = 5k
...	...
n	n*k

So total number of constant time operation =  k+2k+3k....nk = k(1+2+3...n) = k(n(n+1)/2) = O(n^2)

 

So the operation is quadratic on the number of strings to be concatenated. That's not a good efficiency, because you would expect the operation to be O(kn) (there are k*n characters to copy in total). StringBuilder solves this problem. StringBuilder keeps an array of strings to be concatenated, and only builds a new (concatenated) string when required to, hence gives O(kn) - linear - time.

 

public String concatenateManyStrings(String[] strings){

	StringBuilder builder = new StringBuilder();
    
	for(String s: strings){
		s.append(s);
	}
    
    return builder.toString();
}

Easy!

Note that if you know the number of characters of the final string, you should preferrably pass that number to the StringBuilder, as it prevents potential doubling of buffer (cbb explaining this now)