1

I have a very specific question regarding strings in Java. Given a string, I would like to be able to make an array of strings, such that every i'th element is a string consisting of the first i characters of the given string. Like this:

public static String[] substrings(String s){
    String[] list = new String[s.length()];
    list[0] = "" + s.charAt(0);
    for (int i = 1; i < s.length(); i++)
        list[i] = list[i-1] + s.charAt(i);
    return list;
}

But I heared adding strings together with '+' has time complexity O(n). This would mean my method has time complexity O(n²). Another way might be using the StringBuilder object. Like this:

public static String[] substrings(String s){
    String[] list = new String[s.length()];
    StringBuilder sb = new StringBuilder(s.length());
    for (int i = 0; i < s.length(); i++){
        sb.append(s.charAt(i));
        list[i] = sb.toString();
    }
    return list;
}

But I have the feeling that StringBuilder.toString() has a time complexity of O(n), which means the method still has time complexity O(n²). Although I'm not certain about this, so please correct me if I'm wrong.

If I'm right about this though, is there a way to build strings in Java, and have some sort of log of all the values it's had, which doesn't require time complexity O(n²)?

And if not, is there a way of doing this in another programming language, preferably C or C++?

It just feels like a computer should be able to do this, because you are in fact able to do this with numbers. Although it does have more memory complexity with strings, so I wouldn't be too surprised if it isn't possible.

SmileyCraft
  • 257
  • 1
  • 10
  • Those aren't lists (in title), they are arrays. – Andy Turner Sep 29 '16 at 20:55
  • Take a look at [this answer](http://stackoverflow.com/a/4679775/3280538). Making any copy of the string will be an O(n) solution. – flakes Sep 29 '16 at 20:56
  • Not an answer, but interesting trivia. in C++, COW was pretty much encouraged by the standards, but then it got changed, and is not allowed. GCC is incompilant with it until GCC 5. (So, copying strings in C++ with GCC 4.* is O(1)). – amit Sep 29 '16 at 21:02
  • If you want a language which is smarter about data allocation then you should look into languages that focus on immutable types (tend to be functional languages). Mutability prevents code from being smart about data. – flakes Sep 29 '16 at 21:02
  • In any case , if you are writing n strings of length 1 to n , the worst case complexity would be O(n²). – Yogesh Yadav Sep 29 '16 at 21:12

2 Answers2

1

Looking at OpenJKD, StringBuilder.toString() (1) ends up calling new String(char[], offset, count) (2), which calls Arrays.copyOfRange (3), which calls System.arrayCopy. At a certain level, this is going to end up moving n bytes in memory; however, the system is often able to utilize CPU-level block copy commands, which executes more quickly than copying n bytes one-at-a-time.

I think this algorithm is still n^2, since you're copying 1, then 2, then 3, ..., then n bytes. I don't think you can accomplish your goal any more quickly, since you have to copy this many bytes in order to fill out the array.

The string builder implementation is definitely more performant, since at each step, it writes a single byte into an array (that is already sized correctly!), and then copies that array to a different memory location.

Andrew Rueckert
  • 4,858
  • 1
  • 33
  • 44
  • 2
    how would copying "1, then 2, then 3, ..., then n bytes" be Log(n)? – Sleiman Jneidi Sep 29 '16 at 23:04
  • I wrote "n Log(n)", but you're correct, it's still 1/2 n^2, which is n^2. I mistook the pattern 1,2,3,4,n for 1,2,4,8,n, which is what you'd need for nLog(n). Updating my post to correct this. – Andrew Rueckert Sep 30 '16 at 01:07
-1

But, in any case, from a performance point of view, using StringBuilder is better.

I have observed this to be the case when I did toString()s. I observe that building a String using the + operator takes more time than when we use StringBuilder. So everything said and done - even if the time complexity is similar, using StringBuilder is better any day.

Ramana Sarva
  • 293
  • 2
  • 5
  • 20