Leetcode 2315: Count Asterisks

Input: The input consists of a string s which contains lowercase English letters, vertical bars '|', and asterisks '*'.

Example: s = '|*a|*b*|c*|'

Constraints:

• 1 <= s.length <= 1000

• s contains only lowercase English letters, '|', and '*' characters.

• s contains an even number of vertical bars '|'.

Output: Return the number of '*' characters in the string, excluding those between the vertical bars '|'.

Example: For s = '|*a|*b*|c*|', the output is 2.

Constraints:

• Only '*' characters outside of the '|' pairs should be counted.

Goal: The goal is to iterate through the string and count the asterisks '*' outside the pairs of vertical bars '|'.

Steps:

• 1. Traverse the string and track when you encounter a vertical bar '|'.

• 2. When a vertical bar is encountered, skip counting asterisks that appear between this bar and the next one.

• 3. Count the asterisks that are outside these pairs.

Goal: The problem constraints ensure that the string is manageable in size and only contains lowercase letters, vertical bars, and asterisks.

Steps:

• The string will always contain an even number of vertical bars.

• Each vertical bar will belong to a pair.

Assumptions:

• The input string contains at least one vertical bar and may contain other characters, including asterisks.

• Input: s = '|*a|*b*|c*|'

• Explanation: In this example, asterisks inside the vertical bars are excluded. The valid asterisks are those outside the bars, which are counted to give a result of 2.

Approach: The approach involves traversing the string and counting the asterisks that are outside the paired vertical bars '|'.

Observations:

• We need to iterate over the string and keep track of whether we are inside a pair of vertical bars '|'.

• Each time we encounter a '|', we flip the sign to track whether we are inside a pair of bars, and count the asterisks outside.

Steps:

• 1. Initialize a result variable to store the count of valid asterisks.

• 2. Use a sign variable to track whether we are inside a pair of vertical bars.

• 3. Iterate through the string. For each character, if it is an asterisk and we are not inside a vertical bar pair, increment the result.

• 4. Return the final count of valid asterisks.

Empty Inputs:

• The string will not be empty as per the problem constraints.

Large Inputs:

• Handle strings up to 1000 characters efficiently.

Special Values:

• Consider strings where there are no asterisks or where all asterisks are inside vertical bars.

Constraints:

• The string will always contain an even number of vertical bars.

int countAsterisks(string s) {
    int res = 0, sign = 1;
    for (char& c : s)
        if ((sign ^= c == '|') && c == '*')
            res++;
    return res;
}

1 : Function Declaration

int countAsterisks(string s) {

Define the function `countAsterisks` which takes a string `s` and returns an integer representing the number of asterisks '*' in the string that are outside of vertical bars '|'.

2 : Variable Initialization

    int res = 0, sign = 1;

Initialize two variables: `res` to store the count of asterisks and `sign` to track whether we are inside or outside a vertical bar. The `sign` is toggled each time a '|' character is encountered.

3 : For Loop

    for (char& c : s)

Iterate through each character `c` in the string `s` using a range-based for loop.

4 : If Condition Check

        if ((sign ^= c == '|') && c == '*')

Check if the current character is an asterisk '*' and if the `sign` is toggled by encountering a '|' character. The XOR operation toggles `sign` whenever a '|' is found. If the character is '*' and `sign` is correctly positioned, the asterisk is counted.

5 : Increment Count

            res++;

If the condition is met (the character is '*' and not inside '|'), increment the `res` counter by 1.

6 : Return Statement

    return res;

Return the total count of asterisks outside the vertical bars, stored in the `res` variable.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the length of the string, as we iterate through the string once.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1), as we use a constant amount of extra space for tracking the result and sign.

Leetcode 2315: Count Asterisks

Explore →