title: What is the time complexity of Java's String.replace* methods?
body: <p>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.</p>
  
  <p>Ex. I have a string <code>s = "aabbccddeeffcc"</code>. If I do <code>s.replace("cc", "")</code> 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 <code>aabbddeeffcc</code>, <code>aabbccddeeff</code> or <code>aabbddeeff</code>, but which it is is not as important to me.)</p>
  
  <p>I've heard that StringUtils.replace might be a faster method, but couldn't find time complexity for that either.</p>