Watch 10 video solutions for Count Asterisks, a easy level problem involving String. This walkthrough by code Explainer has 1,079 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |