Abstract / Summary

Count the number of asterisks in a string that are not part of a pair where two asterisks are next to each other.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 84% (100k+ submissions).

Typical patterns to solve this problem:

• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a single method countAsterisks. The method receives a string s and returns the number of asterisk characters (*) that appear outside of any pair of vertical bar delimiters (|). The algorithm walks through the input once, maintaining a flag that indicates whether the current position is inside or outside a delimited region, and increments a counter whenever an asterisk is encountered while the flag denotes the outside state.

Core Logic

The method initializes two variables: result to accumulate the count of qualifying asterisks and outside as a boolean flag that tracks the current region. The flag starts as True, meaning the scan begins outside any delimiters.

result  = 0
outside = True

A single for loop iterates over each character c in the input string.

for c in s:

Inside the loop the code distinguishes three cases:

• When the character is a vertical bar, the outside flag is toggled. This flip changes the interpretation of subsequent characters from outside to inside, or vice-versa.

if c == "|":
    outside = not outside

• When the character is an asterisk and the flag indicates the outside region, the counter is incremented.

elif c == "*" and outside:
    result += 1

• All other characters are ignored, allowing the loop to continue without side effects.

After processing the entire string, the method returns the accumulated count.

return result

Edge Cases Handled

The algorithm correctly processes strings that contain no vertical bars. In that situation the outside flag never changes from its initial True value, so every asterisk in the string contributes to the final count.

When the input contains an odd number of vertical bars, the toggling mechanism still works because each bar flips the flag. The final state of outside after the loop does not affect the result; only the state at the moment each asterisk is examined matters. Consequently, strings that end inside an unmatched delimiter are handled without special casing.

Empty strings are also covered. The loop body never executes, leaving result at zero, which is the correct answer for an empty input.

Strings that consist solely of delimiters, asterisks, or any other characters are processed uniformly. The flag toggles only on vertical bars, and asterisks are counted only when the flag is True. This ensures that asterisks appearing immediately after an opening delimiter are excluded, while those after a closing delimiter are included.

Performance Optimizations

The solution achieves optimal traversal by scanning the input exactly once. The use of a simple boolean flag avoids the overhead of more complex data structures such as stacks or counters for nested delimiters. Because the flag toggles on each vertical bar, the algorithm handles arbitrarily long sequences of delimiters with constant additional memory.

Incrementing the result counter only when both conditions (c == "*" and outside) are satisfied eliminates unnecessary arithmetic operations for characters that do not contribute to the answer. The conditional chain (if … elif …) ensures that each character is evaluated at most once, preventing redundant checks.

Overall, the method operates with minimal per-character work and constant auxiliary space, making it well-suited for large input strings.

Imagine that the computer is looking at a long train made of many different shapes. Some of those shapes are stars, and some are special bars that act like little gates.

The computer needs to count how many stars are sitting out in the open, but it has to ignore any stars that are trapped between two of those gate bars. To do this, the computer starts with its counting bucket set to zero and keeps a special rule in its head. It pretends that it is standing outside of a box.

As the computer walks along the train, it looks at every piece one by one. When it sees a gate bar, it flips its rule. If it was standing outside, it steps inside the box, and if it was already inside, it steps back outside.

Whenever the computer finds a star, it checks its rule. If the computer is standing outside the box, it knows the star is safe to count, so it puts that star into the bucket. If the computer is standing inside the box, it just walks past the star and keeps looking for more. This way, only the stars that are not trapped inside the gates get added to the total.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python	Java			C++					TS
	WalkCCC	Python	Java			C++
	leetcode.ca	Python	Java			C++	C	C#	Go	Rust	TS
	Progiez	Python	Java			C++
github	chandansgowda	Python
	charles-wangkai		Java
	DimitrisJim						C
	fartem			Ruby
	fsq					C++
	JoshCrozier				JS
	lkwq007	Python
	varunu28		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, C#, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality