String has four state members: offset, count (number of characters to be used), char, hashcode.
substring() is designed to perform in O(1) by reusing the original char. This can lead to memory leak if the original String is big and the substring() is used to create a small String. A work around is to pass the result of substring() to a new String(substring) constructor.
Starting Java 7 (1.7.0_06) Oracle got rid of offset & count fields, to fix the memory leak. This leads to substring performing in O(n).