Count Asterisks

Easy

Asked by:

4 views

Topics:

Strings

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 '|'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string contain characters other than '*' and '|'?
Is the input string guaranteed to be non-empty?
What should I return if there are no '|' characters in the input string?
Are the '|' characters guaranteed to appear in pairs, or could there be an odd number of them?
Is there a maximum length for the input string?

Brute Force Solution

Approach

The brute force approach to counting asterisks simply means going through the entire input and checking each part individually. We will check each character and increase our count if it's an asterisk. This ensures we find every single asterisk, no matter where it is.

Here's how the algorithm would work step-by-step:

Start at the very beginning of the input.
Look at the first thing you see.
If it's an asterisk, add one to your asterisk count.
Move to the next thing in the input.
Repeat the 'look and count' process until you've checked every single thing in the input.
The final asterisk count is your answer.

Code Implementation

def count_asterisks_brute_force(input_string):
    asterisk_count = 0

    # Iterate through each character of the input string
    for current_character in input_string:

        #Check if the character is an asterisk
        if current_character == '*':

            # Increase the count if current character is asterisk
            asterisk_count += 1

    return asterisk_count

Big(O) Analysis

Time Complexity

O(n) – The described brute force approach iterates through the entire input string once to count asterisks. The cost is directly proportional to the number of characters in the input string, which we can denote as n. Therefore, the time complexity is O(n) because the algorithm performs a constant amount of work for each character in the input.

Space Complexity

O(1) – The provided solution only utilizes a counter variable to keep track of the number of asterisks. This counter requires constant space, irrespective of the input size. No additional data structures like arrays, lists, or hash maps are used. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The goal is to count specific characters within certain segments of a given text string. We'll identify relevant sections of the text and then count only the asterisks in those areas, ignoring the rest. This prevents unnecessary computations.

Here's how the algorithm would work step-by-step:

Examine the text and note the locations of vertical bars, as these mark the boundaries of the sections we care about.
Consider each segment of text between two vertical bars. We only care about the asterisk count in these sections.
For each section found between the vertical bars, carefully count the number of asterisk characters.
Add up the asterisk counts from all the relevant sections.
Provide the total count of asterisks.

Code Implementation

def count_asterisks(input_string):
    asterisk_count = 0
    is_within_bars = False

    for char in input_string:
        if char == '|':
            # Toggle the flag when a bar is encountered.
            is_within_bars = not is_within_bars

        if is_within_bars and char == '*':
            # Only count asterisks when inside vertical bars.
            asterisk_count += 1

    return asterisk_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of size n to find the vertical bars. Then, it iterates within the segments defined by the bars, also of total length n, to count asterisks. Therefore, the time complexity is determined by a single pass through the string, resulting in O(n) time complexity, where n is the length of the input string.

Space Complexity

O(1) – The provided plain English explanation describes iterating through the string and counting asterisks within segments defined by vertical bars. The only auxiliary space used is for a counter variable to store the asterisk count, and potentially a few variables to track the current position and segment boundaries, all of which are constant in size regardless of the input string's length N. No additional data structures that scale with the input string's size are created. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 immediately as there are no characters to process.
String contains only '\|' characters	The count of asterisks should be zero as there are no sections to count in.
String contains no '\|' characters	All asterisks should be counted because the entire string is considered within a single section.
String starts or ends with a '\|' character	The algorithm should correctly identify the start and end of each section, regardless of leading or trailing '\|' characters.
Consecutive '\|' characters exist in the string	These should be treated as valid section delimiters, potentially leading to empty sections.
String contains non-asterisk and non-pipe characters	The algorithm should ignore these characters and only count asterisks between pipes.
Extremely long input string (performance)	Ensure linear time complexity to avoid performance issues with very large inputs.
String consists of a single section (no pipe characters)	Count all asterisks in the string as everything is within one section.

Null or empty input string

How to Handle:

Return 0 immediately as there are no characters to process.

String contains only '|' characters

How to Handle:

The count of asterisks should be zero as there are no sections to count in.

String contains no '|' characters

How to Handle:

All asterisks should be counted because the entire string is considered within a single section.

String starts or ends with a '|' character

How to Handle:

The algorithm should correctly identify the start and end of each section, regardless of leading or trailing '|' characters.

Consecutive '|' characters exist in the string

How to Handle:

These should be treated as valid section delimiters, potentially leading to empty sections.

String contains non-asterisk and non-pipe characters

How to Handle:

The algorithm should ignore these characters and only count asterisks between pipes.

Extremely long input string (performance)

How to Handle:

Ensure linear time complexity to avoid performance issues with very large inputs.

String consists of a single section (no pipe characters)

How to Handle:

Count all asterisks in the string as everything is within one section.