Problem Statement
Count how many times a given substring appears in a string.
Example Inputs
- Input:
"hello hello", "lo"
- Input:
"banana", "na"
- Input:
"aaaaa", "aa"
- Input:
"mississippi", "iss"
JavaScript Method - Using Only String Methods
Approach
To count the occurrences of a substring in a string, we can use the .indexOf() method repeatedly to locate each instance of the substring, updating the starting position after each match.
Steps
- Initialize
count to 0 and position to 0.
- Use a loop to find the substring starting from
position.
- For each occurrence, increment
count, and set position to the next character after the current occurrence.
- Stop the loop when no more occurrences are found.
- Return
count as the total number of occurrences.
Time & Space Complexity
- Time Complexity: O(n*m), where n is the length of the string and m is the length of the substring.
- Space Complexity: O(1), as only a few variables are used.
Code Snippet
Dry Run
Example input: "hello hello", "lo"
- Initialize:
count = 0, position = 0
- First occurrence at index 3 →
count = 1, position = 5
- Second occurrence at index 9 →
count = 2, position = 11
- No more occurrences, exit loop
- Final output:
2
Alternative Approach - Using a Regular Expression
Approach
A regular expression with the global flag (g) allows us to match all occurrences of the substring at once. We can use .match() to get all matches and count them.
Steps
- Use
RegExp with the global flag to match all occurrences of the substring.
- Apply
.match() to find all matches and store them in an array.
- If no matches are found, return 0; otherwise, return the length of the array.
Time & Space Complexity
- Time Complexity: O(n), as
.match() finds all occurrences.
- Space Complexity: O(k), where k is the number of matches found.
Code Snippet
Dry Run
Example input: "hello hello", "lo"
- Use
str.match(/lo/g) → ['lo', 'lo']
- Return
matches.length → 2
Final output: 2
Complexity Analysis
JavaScript Method (Using String Methods)
- Time Complexity: O(n * m)
- Space Complexity: O(1)
Alternative Approach (Using Regular Expression)
- Time Complexity: O(n)
- Space Complexity: O(k)
Conclusion
Counting occurrences of a substring in a string can be done using index-based looping or regular expressions. Regular expressions provide a more concise solution, while the index-based approach offers finer control.