I used StringBuffer instead of String. String is immutable in Java. For the + operation of String, it literally create a new string and pop all the characters into the new one.
For example, you want to append "aaa" and "bb".
For StringBuffer, you create a stringbuffer contains aaa first. That is StringBuffer sb = new StringBuffer("aaa");
And then sb.append("bb"). It will just append "bb" to sb, nothing new is created.
But if you have String str = "aaa" and do str+"bb". First of all, Java will create a new String newStr. This time, the length of character array stored in string object is increased from 3 to 5. And then add "aaabb" to the new character array. So the complexity of this operation (n1 + (n1+n2) + ... (n1+...+nk)) where n1 to nk is the length of each string. That is O(kn_avg^2)
But the complexity of StringBuffer is (n1+n2+....+nk). That is O(kn_avg). (n_avg is the average length of the strings)