Count Asterisks - Solution & Explanation
Problem Statement
You are given a string s, where every two consecutive vertical bars '|' are grouped into a pair. In other words, the 1st and 2nd '|' make a pair, the 3rd and 4th '|' make a pair, and so forth.
Return the number of '*' in s, excluding the '*' between each pair of '|'.
Note that each '|' will belong to exactly one pair.
Example 1:
Input: s = "l|*e*et|c**o|*de|" Output: 2 Explanation: The considered characters are underlined: "l|*e*et|c**o|*de|". The characters between the first and second '|' are excluded from the answer. Also, the characters between the third and fourth '|' are excluded from the answer. There are 2 asterisks considered. Therefore, we return 2.
Example 2:
Input: s = "iamprogrammer" Output: 0 Explanation: In this example, there are no asterisks in s. Therefore, we return 0.
Example 3:
Input: s = "yo|uar|e**|b|e***au|tifu|l" Output: 5 Explanation: The considered characters are underlined: "yo|uar|e**|b|e***au|tifu|l". There are 5 asterisks considered. Therefore, we return 5.
Constraints:
1 <= s.length <= 1000sconsists of lowercase English letters, vertical bars'|', and asterisks'*'.scontains an even number of vertical bars'|'.
Approach Overview
Problem Overview: You receive a string containing lowercase letters, asterisks (*), and pipe characters (|). Pipes appear in pairs and represent sections that should be ignored. The task is to count how many asterisks appear outside those pipe pairs.
Approach 1: Toggle Counting Using a Boolean Flag (Time: O(n), Space: O(1))
Scan the string from left to right while maintaining a boolean flag that tracks whether you are currently inside a pipe section. Every time you encounter a |, flip the flag. When the flag indicates you are outside a pipe pair, count each * you see. The key insight is that pipes always form valid pairs, so toggling state accurately represents whether the current position should be ignored. This approach performs a single linear pass over the string and avoids extra data structures, making it the most efficient solution for this string processing problem.
Approach 2: Use Regular Expression for Pattern Matching (Time: O(n), Space: O(n))
Another option is to remove or ignore substrings enclosed by pipes using a regular expression. A pattern such as \|[^|]*\| matches a complete pipe segment. Replace those matches with an empty string, leaving only characters that should be considered. After that, count the remaining * characters using a simple iteration or built-in count function. This method leverages regular expressions for concise implementation, especially in languages like Python or JavaScript, but it uses extra memory to construct the filtered string.
Both approaches rely on sequential processing rather than complex data structures. The logic is essentially controlled scanning of a string, which is why the optimal runtime remains linear relative to the string length.
Recommended for interviews: The boolean toggle approach is what interviewers expect. It demonstrates that you can track state during iteration and reason about delimiters in a string. The regex approach works and can be concise, but interviewers typically prefer the explicit linear scan because it shows stronger algorithmic clarity and avoids unnecessary allocations.
Approach 1: Toggle Counting Using a Boolean Flag
This approach involves a pass through the string while maintaining a boolean flag to keep track of whether you are inside or outside of a vertical bar pair. You increment the asterisk count only when the flag indicates that you are outside of such a pair.
This C solution uses a simple loop over the string s. The variable inside_bar toggles between 0 and 1 when a '|' is encountered to indicate entry and exit from a pair. Asterisks are counted only when inside_bar is 0.
Complexity
Time complexity: O(n), where n is the length of the string.
Space complexity: O(1), since no additional space is used except for counters.
Approach 2: Use Regular Expression for Pattern Matching
This alternative approach is to use regular expressions to clean out the sections of the string found between the vertical bar pairs and then simply count asterisks in the resulting string.
This Python solution uses the re.sub method to substitute all characters between '|' pairs with an empty string, effectively removing them, and then uses count to find remaining asterisks.
Code
Python
JavaScript
Complexity
Time complexity: O(n), where n represents the input string length.
Space complexity: O(n) due to the construction of the intermediate cleaned string.
Approach 3: Simulation
We define an integer variable ok to indicate whether we can count when encountering *. Initially, ok=1, meaning we can count.
Traverse the string s. If we encounter *, we decide whether to count based on the value of ok. If we encounter |, we toggle the value of ok.
Finally, return the count result.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Toggle Counting Using a Boolean Flag | Time complexity: O(n), where n is the length of the string. |
| Use Regular Expression for Pattern Matching | Time complexity: O(n), where n represents the input string length. |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Toggle Counting Using a Boolean Flag | O(n) | O(1) | Best general solution. Single pass with constant memory. |
| Regular Expression Filtering | O(n) | O(n) | Useful when regex utilities are available and quick string filtering is acceptable. |
Video Solution
2315. Count Asterisks | LEETCODE EASY • code Explainer • 1,107 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Asterisks easy or hard?
Count Asterisks Python/Java solution
How to solve Count Asterisks in O(n)?
What is the best approach for Count Asterisks?
Is Count Asterisks asked at Google/Amazon/Meta?
What data structure is used in Count Asterisks?
What is the time complexity of Count Asterisks?
Ready to solve this problem?
Practice Count Asterisks with our built-in code editor and test cases.
Practice on FleetCode