Count Asterisks

Easy

#2109Time: O(N), where N is the length of the string. The `split` operation takes O(N) time. The subsequent loops iterate through the characters of the even-indexed parts, which in total is at most N characters. Thus, the total time complexity is O(N).Space: O(N). The `split` method creates a new array of strings. The total space required to store these substrings is proportional to the original string's length N.

Data structures

String

Prompt

You are given a string s, where every two consecutive vertical bars '|' are grouped into a pair. In other words, the 1^st and 2^nd '|' make a pair, the 3^rd and 4^th '|' 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 <= 1000
s consists of lowercase English letters, vertical bars '|', and asterisks '*'.
s contains an even number of vertical bars '|'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves splitting the input string s using the vertical bar | as a delimiter. This operation creates an array of substrings. The problem states that asterisks between pairs of | should be excluded. When we split the string by |, the substrings at even indices (0, 2, 4, ...) correspond to the parts of the original string that are outside the pairs of vertical bars. The substrings at odd indices (1, 3, 5, ...) are the parts inside the pairs.

Algorithm

Split the input string s by the delimiter | into an array of strings, parts.\n* Initialize a counter asteriskCount to 0.\n* Loop through the parts array, considering only the elements at even indices (0, 2, 4, ...).\n* For each element at an even index, count the number of asterisks it contains and add it to asteriskCount.\n* Return the final asteriskCount.

Walkthrough

This approach works by first segmenting the string by the | character. This naturally separates the sections inside pairs from those outside. We then only need to process the segments that were originally outside the pairs. The process is as follows:\n\n1. The input string s is split by the delimiter | into an array of strings, let's call it parts.\n2. A counter asteriskCount is initialized to 0.\n3. We loop through the parts array, but only visit the elements at even indices (0, 2, 4, ...), as these correspond to the sections outside the | pairs.\n4. For each of these even-indexed parts, we iterate through its characters.\n5. If a character is an asterisk (*), we increment asteriskCount.\n6. Finally, asteriskCount holds the total count and is returned.\n\nFor example, s = \"l|*e*et|c**o|*de|\" becomes [\"l\", \"*e*et\", \"c**o\", \"*de\", \"\"]. We count asterisks in parts[0] ("l"), parts[2] ("c**o"), and parts[4] (""), yielding a total of 2.\n\n

1java\nclass Solution {\n    public int countAsterisks(String s) {\n        String[] parts = s.split("\\|");\n        int count = 0;\n        // Iterate over the parts that are outside the vertical bars\n        for (int i = 0; i < parts.length; i += 2) {\n            for (char c : parts[i].toCharArray()) {\n                if (c == '*') {\n                    count++;\n                }\n            }\n        }\n        return count;\n    }\n}\n

Complexity

Time

O(N), where N is the length of the string. The `split` operation takes O(N) time. The subsequent loops iterate through the characters of the even-indexed parts, which in total is at most N characters. Thus, the total time complexity is O(N).

Space

O(N). The `split` method creates a new array of strings. The total space required to store these substrings is proportional to the original string's length N.

Trade-offs

Pros

Conceptually simple and easy to understand.
Leverages built-in string manipulation functions, leading to concise code.

Cons

Higher space complexity (O(N)) compared to a single-pass approach.
Can be less performant due to the overhead of creating an array and multiple string objects.

This is the most efficient approach, solving the problem in a single pass through the string. It avoids creating any intermediate data structures by simply keeping track of whether the current character being processed is inside or outside a pair of vertical bars. A state variable, such as a counter for | characters or a boolean flag, is used for this purpose.

Algorithm

Initialize two integer variables: asteriskCount = 0 and pipeCount = 0.\n* Iterate through each character c of the string s.\n* If c is '|', increment pipeCount.\n* If c is '*', check if pipeCount is even. If it is, increment asteriskCount.\n* After the loop finishes, return asteriskCount.

Walkthrough

This optimal solution involves a single traversal of the string. We maintain a state to determine if we are currently inside or outside a pair of vertical bars. This state can be tracked using a simple counter for the | characters encountered.\n\nThe algorithm proceeds as follows:\n\n1. Initialize an asteriskCount to 0 and a pipeCount to 0.\n2. Iterate through each character c of the string from left to right.\n3. If the character c is a |, we've crossed a boundary, so we increment pipeCount.\n4. If the character c is an *, we must decide whether to count it. We check the parity of pipeCount. If pipeCount is even (0, 2, 4, ...), it means we are currently outside a pair, so we increment asteriskCount.\n5. If pipeCount is odd, we are inside a pair, and we do nothing.\n6. After the loop completes, asteriskCount will contain the desired total.\n\nThis method is efficient because it processes each character once without needing to store parts of the string.\n\n

1java\nclass Solution {\n    public int countAsterisks(String s) {\n        int asteriskCount = 0;\n        int pipeCount = 0;\n        for (int i = 0; i < s.length(); i++) {\n            char c = s.charAt(i);\n            if (c == '|') {\n                pipeCount++;\n            } else if (c == '*') {\n                // If pipeCount is even, we are outside a pair.\n                if (pipeCount % 2 == 0) {\n                    asteriskCount++;\n                }\n            }\n        }\n        return asteriskCount;\n    }\n}\n

Complexity

Time

O(N), where N is the length of the string. We perform a single pass over the string.

Space

O(1). We only use a constant amount of extra space for a few counter variables, regardless of the input size.

Trade-offs

Pros

Optimal time complexity of O(N).
Optimal space complexity of O(1).
Highly efficient as it avoids the overhead of creating new data structures.

Cons

While simple for this problem, state management can become complex in more intricate problems.

Solutions

Solution

1public class Solution {2    public int CountAsterisks(string s) {3        int ans = 0, ok = 1;4        foreach(char c in s) {5            if (c == '*') {6                ans += ok;7            } else if (c == '|') {8                ok ^= 1;9            }10        }11        return ans;12    }13}

1class Solution {2public3  int countAsterisks(String s) {4    int ans = 0;5    for (int i = 0, ok = 1; i < s.length(); ++i) {6      char c = s.charAt(i);7      if (c == '*') {8        ans += ok;9      } else if (c == '|') {10        ok ^= 1;11      }12    }13    return ans;14  }15}

1class Solution {2public:3  int countAsterisks(string s) {4    int ans = 0, ok = 1;5    for (char &c : s) {6      if (c == '*') {7        ans += ok;8      } else if (c == '|') {9        ok ^= 1;10      }11    }12    return ans;13  }14};

1class Solution:2    def countAsterisks(self, s: str) -> int: ans, ok = 0, 1 for c in s: if c == "*": ans += ok elif c == "|": ok ^= 1 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem