Java Programs›Strings›Count Occurrences of Substring

Count Occurrences of Substring in Java

intermediate· Strings · String

Problem

Counting occurrences means finding how many times a substring appears in a larger string, moving past each match found so the same characters aren't counted twice.

Given a string and a target substring, count how many times the substring occurs.

Input

"the cat sat on the mat", "at"

Output

Occurrences: 3

Java Program

Java

public class CountSubstringOccurrences {
    public static void main(String[] args) {
        String str = "the cat sat on the mat";
        String sub = "at";
        int count = 0;
        int index = 0;

        while ((index = str.indexOf(sub, index)) != -1) { // searches for the next match starting from the current index
            count++;
            index += sub.length(); // move past this match to avoid re-counting overlaps
        }

        System.out.println("Occurrences: " + count);
    }
}

▶ Run Code

Output

Occurrences: 3

Core Logic

Repeatedly searching from just past the last match, using indexOf() with a starting offset, finds every occurrence in a single left-to-right sweep.

How It Works

1str.indexOf(sub, index) searches for the next occurrence of sub, starting from position index.
2As long as a match is found (the result isn't -1), count is incremented.
3index is advanced by sub.length() after each match, moving the search past the characters just matched.
4The loop stops once indexOf() returns -1, meaning no further occurrences exist.

In "the cat sat on the mat", "at" is found inside 'cat', 'sat', and 'mat' — three non-overlapping matches.

💡

Key Point: Advancing by sub.length() rather than by 1 is what makes this count non-overlapping occurrences — advancing by 1 instead would also catch overlapping matches, like counting "aa" twice in "aaa".

Complexity

Time Complexity: O(n × m)Space Complexity: O(1)

Why: Each call to indexOf() may need to compare up to m characters at every position it tries, and the search restarts just past each match found.

Key Concepts

String.indexOf()while loopsearch offset

Approach 2: Replace Trick

Java

public class CountSubstringOccurrencesTrick {
    public static void main(String[] args) {
        String str = "the cat sat on the mat";
        String sub = "at";
        // Removing every occurrence shrinks the string by (occurrences * sub.length())
        int count = (str.length() - str.replace(sub, "").length()) / sub.length();
        System.out.println("Occurrences: " + count);
    }
}

▶ Run Code

Output

Occurrences: 3

Core Logic

Removing every occurrence of the substring shrinks the string by exactly (occurrences × substring length) — so the occurrence count can be worked backward from that shrinkage.

How It Works

1str.replace(sub, "") deletes every occurrence of sub, producing a shorter string.
2str.length() - replaced.length() gives the total number of characters removed.
3Dividing that difference by sub.length() gives back the number of times sub was removed — the occurrence count.

Removing every "at" from "the cat sat on the mat" (23 characters) leaves "the c s on the m" (17 characters) — a difference of 6, divided by 2 gives 3 occurrences.

💡

Key Point: This is a neat one-liner, but it does the same underlying scan as indexOf() internally — the appeal here is brevity, not a different algorithm.

Complexity

Time Complexity: O(n × m)Space Complexity: O(n)

Why: replace() has to scan the whole string and build an entirely new string with the matches removed, before the length arithmetic can run.

Key Concepts

String.replace()string length arithmetic

← Previous

Count Digits in a String

Count Spaces in a String

Related Programs

Check Palindrome String

Stringsintermediate

Check Pangram

Stringsbeginner

Check String Contains Only Alphabets