algoadvance

You are given a string s that contains some characters and/or asterisks ('*'). You are required to count the number of asterisks ('*') that are not enclosed between pairs of pipe ('|') characters.

More formally, the asterisks to be counted are not:

• Between a pair of pipe characters | that contains zero or more pipe characters.

Example:

• Input: s = "l|*e*et|c**o|*de|"
• Output: 2

Clarifying Questions

1. What characters can the string s contain?
   • The string can contain any ASCII character.
2. Can the string contain an odd number of pipe characters?
   • Yes, the string can contain an odd number of pipe characters, which means all characters after the last | should be taken into account.
3. Is it guaranteed that the input string will be non-empty?
   • Yes, we can assume the input string s is non-empty.

Strategy

1. Use a flag to track whether we are currently between a pair of pipe characters.
2. Initialize a counter to count the valid asterisks (i.e., asterisks not between | pairs).
3. Traverse through the string character by character:
   • Toggle the flag whenever a pipe character is encountered.
   • Increment the counter when an asterisk is encountered if the flag is not set.
4. Return the counter.

Time Complexity

• Time Complexity: O(n), where n is the length of the string s, as we need to traverse the entire string once.
• Space Complexity: O(1), since we are using only a few extra variables regardless of the input size.

Code

Here’s the Python code to solve the problem:

def countAsterisks(s: str) -> int:
    inside_pipes = False
    asterisk_count = 0
    
    for char in s:
        if char == '|':
            inside_pipes = not inside_pipes
        elif char == '*' and not inside_pipes:
            asterisk_count += 1
            
    return asterisk_count

# Example usage:
s = "l|*e*et|c**o|*de|"
print(countAsterisks(s))  # Output: 2

This implementation correctly counts the number of asterisks that are not enclosed between any pairs of pipe characters.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?