Count Asterisks solution and explanation
Google
9 more videos on this problem
2315. Count Asterisks | LEETCODE EASYcode Explainer · 3:31 · 1K views
2315 Count Asterisks | Zero to FAANG | Weekly 296 | Striver SDE Sheet | Shapnesh | WE2Programmers Zone · 8:51 · 810 views
Count Asterisks LeetCode Solution Java ( leetcode 2315 )Engineering Digest · 3:45 · 806 views
2315. Count Asterisks (Leetcode Easy)Programming Live with Larry · 4:10 · 624 views
LeetCode 2315 - Count Asterisks | Java Solution Explained Step-by-Step| Just in 5 minsRecurso · 7:39 · 339 views
LeetCode #2315 | Count AsterisksCode Meant · 7:48 · 218 views
2315. Count Asterisks with python | leetcode with pythonArsalan Ahmed · 7:46 · 162 views
Count Asterisks - LeetCode 2315 - Java Solutionalgobest - Computer Science · 2:03 · 137 views
Count Asterisks (LeetCode 2315 problem) - Java pure code solutionCoding Club Lambda · 1:11 · 108 views
LeetCode 2315 - Count AsterisksKuldeep Patel · 4:29 · 17 views
The problem
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 <= 1000sconsists of lowercase English letters, vertical bars'|', and asterisks'*'.scontains an even number of vertical bars'|'.
Approach overview
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 1: Toggle Counting Using a Boolean Flag
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.
def count_asterisks(s: str) -> int:
count = 0
inside_bar = False
for char in s:
if char == '|':
inside_bar = not inside_bar
elif char == '*' and not inside_bar:
count += 1
return count
# Example usage
s = "l|*e*et|c**o|*de|"
print(count_asterisks(s)) # Output: 2public class CountAsterisks {
public static int countAsterisks(String s) {
int count = 0;
boolean insideBar = false;
for (char ch : s.toCharArray()) {
if (ch == '|') {
insideBar = !insideBar;
} else if (ch == '*' && !insideBar) {
count++;
}
}
return count;
}
public static void main(String[] args) {
String s = "l|*e*et|c**o|*de|";
System.out.println(countAsterisks(s)); // Output: 2
}
}#include <iostream>
#include <string>
int countAsterisks(const std::string& s) {
int count = 0;
bool inside_bar = false;
for (char ch : s) {
if (ch == '|') {
inside_bar = !inside_bar;
} else if (ch == '*' && !inside_bar) {
count++;
}
}
return count;
}
int main() {
std::string s = "l|*e*et|c**o|*de|";
std::cout << countAsterisks(s) << std::endl; // Output: 2
return 0;
}function countAsterisks(s) {
let count = 0;
let insideBar = false;
for (let char of s) {
if (char === '|') {
insideBar = !insideBar;
} else if (char === '*' && !insideBar) {
count++;
}
}
return count;
}
// Example usage
let s = "l|*e*et|c**o|*de|";
console.log(countAsterisks(s)); // Output: 2;#include <stdio.h>
int countAsterisks(char *s) {
int count = 0;
int inside_bar = 0;
while (*s) {
if (*s == '|') {
inside_bar = !inside_bar;
} else if (*s == '*' && !inside_bar) {
count++;
}
s++;
}
return count;
}
int main() {
char s[] = "l|*e*et|c**o|*de|";
printf("%d\n", countAsterisks(s)); // Output: 2
return 0;
}using System;
class CountAsterisks {
public static int CountAsterisksInString(string s) {
int count = 0;
bool insideBar = false;
foreach (char ch in s) {
if (ch == '|') {
insideBar = !insideBar;
} else if (ch == '*' && !insideBar) {
count++;
}
}
return count;
}
static void Main() {
string s = "l|*e*et|c**o|*de|";
Console.WriteLine(CountAsterisksInString(s)); // Output: 2
}
}In Python, this solution leverages the flexibility of boolean logic to toggle counting of asterisks outside vertical bar pairs.
Time complexity: O(n), as it processes each character.
Space complexity: O(1), with only minimal variable usage for flags.
Approach 2: Use Regular Expression for Pattern Matching
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.
import re
def count_asterisks_regex(s: str) -> int:
cleaned = re.sub(r'\|[^|]*\|', '', s)
return cleaned.count('*')
# Example usage
s = "l|*e*et|c**o|*de|"
print(count_asterisks_regex(s)) # Output: 2function countAsterisksRegex(s) {
let cleaned = s.replace(/\|[^|]*\|/g, '');
return (cleaned.match(/\*/g) || []).length;
}
// Example usage
let s = "l|*e*et|c**o|*de|";
console.log(countAsterisksRegex(s)); // Output: 2;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.
Time complexity: O(n), where n represents the input string length.
Space complexity: O(n) due to the construction of the intermediate cleaned string.
Approach 3: Simulation
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).
function countAsterisks(s: string): number {
let ans = 0;
let ok = 1;
for (const c of s) {
if (c === '*') {
ans += ok;
} else if (c === '|') {
ok ^= 1;
}
}
return ans;
}func countAsterisks(s string) (ans int) {
ok := 1
for _, c := range s {
if c == '*' {
ans += ok
} else if c == '|' {
ok ^= 1
}
}
return
}impl Solution {
pub fn count_asterisks(s: String) -> i32 {
let mut ans = 0;
let mut ok = 1;
for &c in s.as_bytes() {
if c == b'*' {
ans += ok;
} else if c == b'|' {
ok ^= 1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Toggle Counting Using a Boolean Flag | Time complexity: O(n), as it processes each character. |
| Use Regular Expression for Pattern Matching | Time complexity: O(n), where n represents the input string length. |
| Simulation | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Count Asterisks easy or hard?
Count Asterisks is classified as an Easy problem on LeetCode with a high acceptance rate above 80%. The challenge mainly tests careful string traversal and state tracking rather than advanced algorithms.
Count Asterisks Python/Java solution
In Python or Java, iterate through the string and maintain a boolean flag that flips when encountering '|'. Increment a counter when the character is '*' and the flag indicates you are outside a pipe pair. The logic remains identical across languages and runs in O(n) time.
How to solve Count Asterisks in O(n)?
Traverse the string once while maintaining a boolean variable that indicates whether the current position is inside a pipe pair. Toggle the variable whenever a '|' character appears. If the variable shows you are outside a pipe section and the character is '*', increment the counter.
What is the best approach for Count Asterisks?
The boolean toggle scan is the best approach. Iterate through the string once and flip a flag whenever a pipe character '|' appears. Count '*' only when the flag indicates you are outside a pipe pair. This runs in O(n) time with O(1) extra space.
Is Count Asterisks asked at Google/Amazon/Meta?
Count Asterisks is categorized as an easy string-processing problem commonly used in coding practice and interview preparation. Variants of delimiter parsing and state tracking appear in interviews at companies like Amazon and Google, especially for testing string traversal logic.
What data structure is used in Count Asterisks?
No complex data structure is required. The solution relies on simple string traversal with a boolean state variable and a counter. The focus is on correctly handling delimiters while scanning the string sequentially.
What is the time complexity of Count Asterisks?
The optimal solution runs in O(n) time, where n is the length of the string. Each character is processed exactly once during a single left-to-right scan. Space complexity is O(1) because only a counter and a boolean flag are maintained.