Count Asterisks

Difficulty: Easy | Acceptance: 83.40% | Paid: No Topics: String

You are given a string s, where every two consecutive vertical bars ’|’ are grouped. In other words, the first and second ’|’ make a pair, the third and fourth ’|’ make a pair, and so forth.

Return the number of '' characters in s, excluding the '' between each pair of ’|‘.

Note that each ’|’ will belong to exactly one pair.

• Examples
• Constraints
• Single Pass with Flag
• Split and Count
• Two Pass with Index Tracking

Examples

Input: s = "l|*e*et|c**o|*de|"
Output: 2
Explanation: The '*' between the first and second '|' is excluded, and the '*' between the third and fourth '|' is excluded. The remaining '*' are counted.

Input: s = "iamprogrammer"
Output: 0
Explanation: There are no '*' in the string.

Input: s = "yo|uar|e**|b|e***au|tifu|l"
Output: 5
Explanation: The '*' between the second and third '|' is excluded, and the '*' between the fifth and sixth '|' is excluded. The remaining '*' are counted.

Constraints

1 <= s.length <= 1000
s consists of lowercase English letters, vertical bars '|', and asterisks '*'.
s contains an even number of vertical bars '|'.

Single Pass with Flag

Intuition Use a boolean flag to track whether we’re inside a pair of bars. Toggle the flag when encountering ’|’ and only count asterisks when outside bars.

Steps

• Initialize count to 0 and inside flag to false
• Iterate through each character in the string
• If character is ’|’, toggle the inside flag
• If character is ’*’ and not inside, increment count
• Return the final count

class Solution:
    def countAsterisks(self, s: str) -> int:
        count = 0
        inside = False
        for c in s:
            if c == '|':
                inside = not inside
            elif c == '*' and not inside:
                count += 1
        return count

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1)
• Notes: Optimal solution with constant space overhead

Split and Count

Intuition Split the string by ’|’ to get segments. Asterisks in even-indexed segments (0, 2, 4, …) are outside bars and should be counted.

Steps

• Split the string by ’|’ delimiter
• Iterate through segments at even indices only
• Count asterisks in each selected segment
• Return the total count

class Solution:
    def countAsterisks(self, s: str) -> int:
        segments = s.split('|')
        count = 0
        for i in range(0, len(segments), 2):
            count += segments[i].count('*')
        return count

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for storing split segments
• Notes: More readable but uses extra memory for the split array

Two Pass with Index Tracking

Intuition First find all positions of ’|’ in the string, then count asterisks that are not between any pair of bars by checking their position against bar indices.

Steps

• Find and store all positions of ’|’ in the string
• Iterate through the string again
• For each asterisk, check if it falls between any pair of bars
• Count only asterisks outside all bar pairs
• Return the final count

class Solution:
    def countAsterisks(self, s: str) -> int:
        bar_positions = [i for i, c in enumerate(s) if c == '|']
        count = 0
        for i, c in enumerate(s):
            if c == '*':
                inside = False
                for j in range(0, len(bar_positions), 2):
                    if j + 1 < len(bar_positions) and bar_positions[j] < i < bar_positions[j + 1]:
                        inside = True
                        break
                if not inside:
                    count += 1
        return count

Complexity

• Time: O(n²) in worst case where n is the length of the string
• Space: O(n) for storing bar positions
• Notes: Less efficient due to nested loops, but demonstrates an alternative approach