Internal working of replaceAll() function in String class, Java

I have visited multiple websites just to know the internal workings of any regex function used in the String class like split() and replaceAll().

Problem statement is available here: https://www.hackerearth.com/practice/basic-programming/implementation/basics-of-implementation/practice-problems/algorithm/one-string-no-trouble-37037871/

My code:

String s = "abaaccasdraaaadsfd";
s = s.replaceAll("(.)\{1,}", "$17$1");
String[] s2 = s.split("7");
int len = 0;
for(String a : s2) {
    if(a.length() > len) {
        len = a.length();
    }
}
System.out.println(len);

General code online:

String s = "abaaccasdraaaadsfd";
int count=0;
int max=0;
for(int i=1;i<str.length();i++){
    char ch =str.charAt(i-1);
    char ch1=str.charAt(i);
    if(ch!=ch1){
        count++;
        if(max<count){
            max=count;
        }
    }else{
        count=0;
    }
}
System.out.println(max+1);

I want to understand if the regex internally operates on O(n) where n is the length of the string then my code (using regex) is similar to general online code (using for loop) with respect to time complexity.

Thanks in advance.

Regexes are way too complex for such a simplistic analysis.

There is a thing called a Thompson/NFA regexp parser. Such a regexp parser has O(n+m) performance, where n is the length of the regexp, and m is the length of the input string. However, TNFAs cannot deal with backreferences, various lookaheads/lookbacks, and have other issues. Once you start using these 'TNFA disqualifying' features in regexp, it is in fact impossible to squeeze o(n+m) performance out of your regexp engine. The proof for this is fairly trivial. This regexp:

/^1?$|^(11+?)\1+$/

will match input strings whose length is a prime number and consists solely of '1' symbols. It will fail other things.

This job (check if prime number) cannot be done in O(n). Therefore, any regexp parser that can run the above regexp cannot be O(n+m), QED.

Now, a relevant question would be: If the input regexp uses solely the basic features, such that the regexp could be processed by a Thompson/NFA style state machine, does java use that, falling back to a simple backtracking implementation otherwise?

The answer seems irrelevant to your question because you ARE using backtracking here. However, if memory serves, java doesn't ship with a TNFA implementation and will always use a backtracker. This is, however, not written into the spec, so some future version could feasibly switch imlementations intelligently depending on the features used in the input regexp. The current (as of JDK14) implementation fully supports the entire featureset as explained in the javadoc of the java.util.regexp.Pattern class (which includes features that a TNFA engine cannot do, such as backtracking), and it does mean that certain regexes take many orders of magnitude longer in java's regex engine vs. a Thompson/NFA one.

More info about Thompson / NFA.

re2j is a java implementation of Thompson/NFA. Use this if you want guaranteed linear performance (O(n+m)) regular expressions in java. As is mathematically dictates, re2j doesn't support backreferences and a few other things (see the site for the list), so it cannot run your (.)\\1{1,} expression - that's because mathematically speaking it isn't possible to do that in O(n) time.