LeetCode 2315 - Count Asterisks

The problem gives us a string s containing lowercase English letters, vertical bars '|', and asterisks ''. The key rule is that every two consecutive vertical bars form a pair. Any asterisk located between the two bars of a pair must be ignored when counting.

leetcodeeasystring

LeetCode Problem 2315

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem gives us a string s containing lowercase English letters, vertical bars '|', and asterisks '*'. The key rule is that every two consecutive vertical bars form a pair. Any asterisk located between the two bars of a pair must be ignored when counting.

Our task is to count only the asterisks that are outside these paired bar sections.

Another way to think about the problem is that the string alternates between two modes:

  • Outside a pair of bars, where '*' characters should be counted
  • Inside a pair of bars, where '*' characters should be ignored

Each time we encounter a vertical bar '|', we switch between these two modes.

For example, consider:

l|*e*et|c**o|*de|

The substring *e*et lies between the first pair of bars, so its asterisks are ignored. The substring *de lies between the second pair of bars, so those are ignored as well. Only the two asterisks in c**o are counted.

The constraints are small:

  • 1 <= s.length <= 1000
  • The string contains only lowercase letters, |, and *
  • The number of vertical bars is guaranteed to be even

Since the maximum length is only 1000, even less efficient approaches could work. However, the problem naturally suggests a simple linear scan solution.

Some important edge cases include:

  • Strings with no asterisks at all
  • Strings with no vertical bars
  • Strings where all asterisks are inside bar pairs
  • Strings where all asterisks are outside bar pairs
  • Consecutive bar pairs with no characters between them
  • Strings beginning or ending with bars

The guarantee that the number of bars is even is important because it ensures every opening section has a matching closing section.

Approaches

Brute Force Approach

A brute force solution could first identify every pair of vertical bars and record all character ranges that should be ignored. After determining these excluded intervals, we could iterate through the string again and count only the asterisks that are not inside any excluded range.

One possible implementation is:

  1. Store the indices of all '|' characters.
  2. Group them into pairs.
  3. Mark all indices inside those pairs as excluded.
  4. Iterate through the string and count valid '*' characters.

This approach is correct because every ignored region is explicitly identified before counting begins.

However, this method is unnecessarily complicated. It may also require additional space to store excluded ranges or markers. Although the constraints are small enough that this would still pass, the problem can be solved much more elegantly with a single pass.

Optimal Approach

The key observation is that we do not actually need to store ranges between bars. We only need to know whether the current position is inside or outside a bar pair.

We can maintain a boolean flag:

  • inside_bars = False initially
  • Every time we encounter '|', toggle the flag
  • If we encounter '*' while inside_bars is False, increment the answer

This works because the bars always come in valid pairs. Each '|' flips the current counting state.

The solution becomes a straightforward linear scan with constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Stores bar positions or excluded ranges before counting
Optimal O(n) O(1) Single pass using a boolean state

Algorithm Walkthrough

  1. Initialize a counter variable asterisk_count to 0. This will store the number of valid asterisks outside bar pairs.
  2. Initialize a boolean variable inside_bars to False. This variable tracks whether the current character lies inside a paired bar section.
  3. Traverse the string character by character.
  4. For each character:

  • If the character is '|', toggle the value of inside_bars.

  • If we were outside a pair, we now enter a pair.

  • If we were inside a pair, we now exit the pair.

  • Else if the character is '*' and inside_bars is False, increment asterisk_count.

  • All lowercase letters can simply be ignored because they do not affect the answer.

  1. After processing the entire string, return asterisk_count.

Why it works

The algorithm maintains the invariant that inside_bars correctly represents whether the current position lies between a matching pair of vertical bars.

Since every '|' belongs to exactly one pair, toggling the state at each bar correctly tracks whether asterisks should currently be ignored or counted. Therefore, every counted asterisk is outside all bar pairs, and every ignored asterisk is inside a bar pair.

Python Solution

class Solution:
    def countAsterisks(self, s: str) -> int:
        asterisk_count = 0
        inside_bars = False

        for char in s:
            if char == '|':
                inside_bars = not inside_bars
            elif char == '*' and not inside_bars:
                asterisk_count += 1

        return asterisk_count

The implementation directly follows the algorithm described earlier.

The variable asterisk_count stores the final answer. The boolean inside_bars tracks whether the current scan position lies between a matching pair of vertical bars.

As we iterate through the string:

  • Encountering '|' flips the state
  • Encountering '*' increments the answer only if we are currently outside a bar pair
  • Letters are ignored because they do not affect counting

The implementation is concise because the problem naturally maps to state tracking during a single traversal.

Go Solution

func countAsterisks(s string) int {
    asteriskCount := 0
    insideBars := false

    for _, char := range s {
        if char == '|' {
            insideBars = !insideBars
        } else if char == '*' && !insideBars {
            asteriskCount++
        }
    }

    return asteriskCount
}

The Go implementation is nearly identical to the Python version.

One minor language-specific difference is that Go iterates over the string using range, which returns runes. Since all characters in this problem are ASCII, rune handling introduces no complications.

No special handling for nil or empty input is required because the constraints guarantee at least one character.

Worked Examples

Example 1

Input:

s = "l|*e*et|c**o|*de|"
Character inside_bars Action Count
l False Ignore 0
| True Enter bar section 0
* True Ignore 0
e True Ignore 0
* True Ignore 0
e True Ignore 0
t True Ignore 0
| False Exit bar section 0
c False Ignore 0
* False Count 1
* False Count 2
o False Ignore 2
| True Enter bar section 2
* True Ignore 2
d True Ignore 2
e True Ignore 2
| False Exit bar section 2

Final answer:

2

Example 2

Input:

s = "iamprogrammer"
Character inside_bars Action Count
i False Ignore 0
a False Ignore 0
m False Ignore 0
p False Ignore 0
r False Ignore 0
o False Ignore 0
g False Ignore 0
r False Ignore 0
a False Ignore 0
m False Ignore 0
m False Ignore 0
e False Ignore 0
r False Ignore 0

Final answer:

0

Example 3

Input:

s = "yo|uar|e**|b|e***au|tifu|l"
Character inside_bars Action Count
y False Ignore 0
o False Ignore 0
| True Enter section 0
u True Ignore 0
a True Ignore 0
r True Ignore 0
| False Exit section 0
e False Ignore 0
* False Count 1
* False Count 2
| True Enter section 2
b True Ignore 2
| False Exit section 2
e False Ignore 2
* False Count 3
* False Count 4
* False Count 5
a False Ignore 5
u False Ignore 5
| True Enter section 5
t True Ignore 5
i True Ignore 5
f True Ignore 5
u True Ignore 5
| False Exit section 5
l False Ignore 5

Final answer:

5

Complexity Analysis

Measure Complexity Explanation
Time O(n) The string is scanned exactly once
Space O(1) Only a few variables are used

The algorithm performs a single linear traversal through the input string. Each character is processed exactly once, so the runtime grows proportionally to the string length.

The memory usage remains constant because we only store two variables: the answer counter and the boolean state tracking whether we are inside a bar pair.

Test Cases

solution = Solution()

assert solution.countAsterisks("l|*e*et|c**o|*de|") == 2
# Basic example with ignored and counted asterisks

assert solution.countAsterisks("iamprogrammer") == 0
# No asterisks present

assert solution.countAsterisks("yo|uar|e**|b|e***au|tifu|l") == 5
# Multiple bar sections

assert solution.countAsterisks("***") == 3
# All asterisks counted

assert solution.countAsterisks("|***|") == 0
# All asterisks ignored

assert solution.countAsterisks("|a|*|b|**") == 3
# Mixed counted and ignored regions

assert solution.countAsterisks("||***") == 3
# Empty bar section followed by counted asterisks

assert solution.countAsterisks("*|*|*") == 2
# Single ignored asterisk in the middle

assert solution.countAsterisks("|*||*|") == 0
# Multiple adjacent bar pairs

assert solution.countAsterisks("abc") == 0
# No bars and no asterisks

assert solution.countAsterisks("*") == 1
# Smallest meaningful counting case
Test Why
`"l _e_et
"iamprogrammer" No asterisks
`"yo uar
"***" All asterisks counted
`" ***
`" a
`"
`"* *
`" *
"abc" No special characters
"*" Minimum nontrivial case

Edge Cases

One important edge case is a string with no vertical bars at all, such as "***" or "abc". A naive implementation that assumes bars always exist could fail or unnecessarily complicate the logic. The current implementation handles this naturally because inside_bars remains False for the entire traversal, so all asterisks are counted correctly.

Another important edge case is when all asterisks are inside a bar pair, such as "|***|". It is easy to accidentally count these if the state transition logic is incorrect. The implementation correctly toggles into ignored mode after the first '|' and back out after the second '|', ensuring all interior asterisks are skipped.

A third important edge case is adjacent or empty bar pairs, such as "||***" or "|*||*|". These cases can expose bugs in implementations that incorrectly assume there must be characters between bars. Since the algorithm simply toggles state whenever a bar appears, empty sections are handled correctly without requiring any special logic.

A final edge case is strings beginning or ending with bars. For example, "|abc|" or "*|abc|". Incorrect implementations might accidentally count characters after the final bar or mishandle the initial transition. The boolean state approach cleanly handles both scenarios because each bar consistently flips the current mode.*