1

I'm trying to find the most efficient way of removing a character sequence in Java. Note that I don't care if I only remove one instance of the sequence or all of them as long as it is efficient.

Ex. I have a string s = "aabbccddeeffcc". If I do s.replace("cc", "") am I correct in assuming that it is constant time? If not, is there an efficient way of doing this? (The output of this operation could be aabbddeeffcc, aabbccddeeff or aabbddeeff, but which it is is not as important to me.)

I've heard that StringUtils.replace might be a faster method, but couldn't find time complexity for that either.

Ryan
  • 2,869
  • 2
  • 12
  • 20
  • Just measure it with either a (correctly implemented !) micro benchmark or a profiler. Then you will know if it makes sense to tune this. – Marged Oct 22 '15 at 20:14
  • 2
    Java doesn't document what the complexity is. However, the Oracle JVM includes the source.jar with the JDK classes source code, and of course there's OpenJDK where you can see how they implement it. You can compare them with StringUtils implementation by looking at their source code. – Will Hartung Oct 22 '15 at 20:14
  • 1
    Unless you're working with strings that have fixed-width encoding and replacing a single character, there is no way any string replace function is constant time. – w.brian Oct 22 '15 at 20:15
  • See also http://stackoverflow.com/questions/16228992/commons-lang-stringutils-replace-performance-vs-string-replace . Note that `String.replace(CharSequence,CharSequence)` is implemented with the same Pattern matching as the siblings that accept regular expressions. – Andy Thomas Oct 22 '15 at 20:34

1 Answers1

2

According to me its probability is O(n)

Sandeep s
  • 69
  • 4
  • searching a substring inside a string can be done in linear time using the KMP algorithm which is the most efficient. Replacing in the worst case will take linear time as well. So overall time complexity: O(n) Here n is dependent on the string str. In the worst case, it will end up traversing the whole string and still not find the search value given to the replace function. – Pavan May 30 '20 at 08:35
  • @Pavan next time just paste the link of the answer you're copy pasting from. Way more helpful. https://stackoverflow.com/questions/47209406/what-is-the-time-complexity-or-big-o-notation-for-str-replace-built-in-funct – Ayush Feb 24 '21 at 15:39