algoadvance

You are given a string s consisting of lowercase English letters and digits. In this string, there are some words and some numbers, which are separated by a single space. Your task is to determine if the numbers within the string are in ascending order.

Specifically, you should:

• Ignore the words and only consider the numbers.
• Check if the sequence of numbers in the string is strictly increasing.

Clarifying Questions

1. Can the numbers be negative or zero?
   • No, as per the typical interpretation of the problem. Numbers are positive.
2. Will the string always contain at least one number?
   • There are no specific constraints that ensure the presence of numbers always. If there are no numbers, it would be considered trivially non-ascending.
3. Could there be multiple spaces between words?
   • As per the problem statement, words and numbers are separated by a single space.
4. Is the input string guaranteed to be non-empty?
   • Yes.

Strategy

1. Parse the string s and extract only the numbers.
2. Convert these numbers from string format to integers.
3. Check if the list of integers is in strictly ascending order.

Code

def are_numbers_ascending(s: str) -> bool:
    # Split the string by spaces
    tokens = s.split()
    
    # Extract numbers in integer form
    numbers = [int(token) for token in tokens if token.isdigit()]
    
    # Check if numbers are in strictly ascending order
    return all(earlier < later for earlier, later in zip(numbers, numbers[1:]))

# Example:
print(are_numbers_ascending("1 box has 3 blue 4 red 6 green and 12 yellow marbles")) # True
print(are_numbers_ascending("hello world 5 x 6")) # True
print(are_numbers_ascending("4 5 11 26 are the numbers")) # True
print(are_numbers_ascending("7 is later than 4 but not 3")) # False

Time Complexity

The time complexity of this solution is:

• O(n), where n is the number of tokens (words + numbers) in the string s, for splitting and iterating over the tokens.
• Additionally, the conversion and comparison operations are linear with respect to the number of numeric tokens. Thus, the total time complexity is O(n).

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?