# Two approaches to count occurrences of one char in a String in Java

I have two approaches:

First Approach:

int count =0;
for(int i = 0; i < text.length(); i++) {
if(text.charAt(i) == charToCheck){
count++;
}
}
System.out.println(count);


Second Approach:

count = text.length() - text.replaceAll(
String.valueOf(charToCheck),"")
.length();
System.out.println(count);


Which one is fast w.r.t Time & Space Complexity? Why?

Are there any more approaches (which I am not aware of)? If yes, Please let me know.

• What do you mean by Time & Space Complexity? If it's Landau notation you seek, the first one is obviously O(n) for time and O(1) for space. The second one is probably O(n) time and O(n) space (because a second String is constructed, which, on worst case, has n chars), but this depends on the implementation of replaceAll. – Ben Steffan Jul 1 '17 at 13:21
• Yes, i did wanted to know its Bachmann–Landau notation. Well, thank you for updating me about it. – Firoz Memon Jul 1 '17 at 13:30

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.
[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.]
• @FirozMemon As I said, no. You cannot achieve anything below O(n), because you always need to look at each char at least once. If you have n chars, that's n operations, which means O(n) is the theoretical minimum. I advise you to refresh your knowledge on Landau notation. – Ben Steffan Jul 1 '17 at 13:36