algoadvance

Leetcode 2315. Count Asterisks

Problem Statement

You are given a string s, which contains | (pipe) and * (asterisk) characters. We want to determine the number of asterisks in the string that are not enclosed between pairs of pipe characters.

A pair of pipe characters is considered to enclose everything between them if there is an even number of | characters. For example, in the string "|**|*|**|", only the first two and the last asterisk are enclosed by a pair of pipes.

Clarifying Questions

1. Input Constraints:
   • What is the maximum length of the string s?
     • The string length will be between 1 and 1000.
2. Character Guarantee:
   • Can the string have other characters apart from | and *?
     • Yes, it can contain other characters, but we only care about | and *.
3. Pipe Pair Definition:
   • Is the enclosure limited strictly between pipe pairs, even though they are nested?
     • Yes, only consider characters between each pair of pipes.

Strategy

1. Initialize Counters:
   • Have a counter for asterisks that are not enclosed by pipe characters.
   • Maintain a variable to track whether the current character is within pipe-enclosed sections.
2. Iterate Through the String:
   • For each character, check if it is a |. Toggle the inside-pipes flag.
   • If it is an asterisk (*) and we are not inside a pair of pipes, increment the asterisk counter.
3. Edge Cases:
   • Handle strings without any pipes.
   • Handle strings with no *.

Code

#include <iostream>
#include <string>

int countAsterisks(std::string s) {
    int asteriskCount = 0;
    bool insidePipes = false;

    for (char c : s) {
        if (c == '|') {
            insidePipes = !insidePipes;
        } else if (c == '*' && !insidePipes) {
            asteriskCount++;
        }
    }

    return asteriskCount;
}

int main() {
    std::string s = "l|*e*et|c**o|*de|";
    std::cout << "Count of asterisks not enclosed by pipes: " << countAsterisks(s) << std::endl;
    return 0;
}

Time Complexity

• Time Complexity: O(n), where n is the length of the string s. We only make a single pass through the string, checking each character.
• Space Complexity: O(1), as we are only using a few variables to store the current state and the count of asterisks.

This solution ensures that we count only the asterisks that are outside of any pipe-enclosed section efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?