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 <= 1000s consists of lowercase English letters, vertical bars '|', and asterisks '*'.s contains an even number of vertical bars '|'.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.
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.
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.
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.
Python
JavaScript
Time complexity: O(n), where n represents the input string length.
Space complexity: O(n) due to the construction of the intermediate cleaned string.
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).
| 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 | — |
| 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. |
2315. Count Asterisks | LEETCODE EASY • code Explainer • 1,079 views views
Watch 9 more video solutions →Practice Count Asterisks with our built-in code editor and test cases.
Practice on FleetCode