Two approaches to count occurrences of one char in a String in Java
As I stated in the comments, both of your approaches have a time complexity of O(n), but your first approach has a O(1) space complexity whilst your second one requires O(n) space in the worst case, because replaceAll creates a copy with all the matches removed.  

From complexity point of view, your first approach is basically ideal. In order to replace all occurrences of a char, you at least have to iterate every char in your input once, which corresponds to O(n) time complexity. Also, space complexity is, as stated, O(1) which is, obviously, the best case.



[Note: Java makes no guarantees about the time and space complexity of methods. Thus, replaceAll could, in theory, also have a much worse time and space complexity if not implemented well. I assumed that it runs in O(n) (which is the best case) when matching on a single char only. This fact, of course, makes the second approach even worse.]