I have written a code to recursively remove the adjacent duplicates from a string
class Solution{
String rremove(String s) {
// code here
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < s.length()) {
char currentChar = s.charAt(i);
int j = i + 1;
// Find the index of the next different character
while (j < s.length() && s.charAt(j) == currentChar) {
j++;
}
// If adjacent duplicates found, skip them
if (j - i > 1) {
i = j;
} else {
sb.append(currentChar);
i++;
}
}
String result = sb.toString();
// If result string is different from original, recursively call the function
if (!result.equals(s)) {
return rremove(result);
}
return result;
}
Now, I want to understand the time complexity of this code as the number of recursive calls is not fixed here, hence got quite confused looking at the code. Although, each method call is O(n), but with the depth of recursion, it gets uncertain. Hence, please help me understand the best case and worst case scenarion for this code.
The code is from GFG with this title “Recursively remove all adjacent duplicates “