Problem Description

You are given a sentence that contains only lowercase letters ('a' to 'z'), digits ('0' to '9'), hyphens ('-'), punctuation marks ('!', '.', and ','), and spaces (' '). The sentence can be split into one or more tokens using spaces as separators.

A token is considered a valid word if it satisfies all three of the following conditions:

1. No digits allowed: The token can only contain lowercase letters, hyphens, and/or punctuation marks. It cannot contain any digits.

2. Hyphen rules:

   • There can be at most one hyphen '-' in the token
   • If a hyphen is present, it must be surrounded by lowercase letters on both sides
   • Examples: "a-b" is valid, but "-ab" and "ab-" are not valid

3. Punctuation rules:

   • There can be at most one punctuation mark ('!', '.', or ',') in the token
   • If a punctuation mark is present, it must be at the end of the token
   • Examples: "ab,", "cd!", and "." are valid, but "a!b" and "c.," are not valid

Valid word examples include: "a-b.", "afad", "ba-c", "a!", and "!".

Given a string sentence, you need to count and return the total number of valid words in the sentence.

Intuition

The problem asks us to validate each word in a sentence according to specific rules. The natural approach is to break down the problem into smaller, manageable parts.

First, we need to separate the sentence into individual tokens since spaces are the delimiters. Python's split() method handles this perfectly, automatically dealing with multiple consecutive spaces.

For each token, we need to validate it against three rules. The key insight is that we can check these rules character by character in a single pass through each token:

1. Digit check: If we encounter any digit, we can immediately reject the token.

2. Hyphen validation: We need to track if we've already seen a hyphen (using a boolean flag st). When we encounter a hyphen, we check:

   • Is this the first hyphen? (if st is already True, it's invalid)
   • Is it at the beginning or end? (positions 0 or len(s)-1 are invalid)
   • Are the characters immediately before and after it letters? (we can check s[i-1] and s[i+1])

3. Punctuation validation: Punctuation marks are only valid at the end of the token. So if we find a punctuation mark at any position other than the last (i < len(s) - 1), the token is invalid.

By combining these checks in a single traversal of each token, we can efficiently determine validity. The beauty of this approach is that we can return False as soon as we find any violation, making it efficient. If we complete the traversal without finding any violations, the token is valid.

Finally, we count all valid tokens using a simple sum comprehension: sum(check(s) for s in sentence.split()), where the boolean results (True for valid, False for invalid) are automatically converted to 1s and 0s for counting.

Solution Approach

The solution uses a simulation approach where we validate each word according to the given rules. Here's the step-by-step implementation:

Step 1: Split the sentence into tokens

sentence.split()

This automatically handles multiple spaces and gives us individual tokens to validate.

Step 2: Create a validation function for each token

We define a helper function check(s: str) that validates a single token. The function uses a boolean variable st to track whether we've already encountered a hyphen.

Step 3: Character-by-character validation

For each character c at position i in the token s, we perform the following checks:

1. Digit check:

   if c.isdigit():
       return False

   If any character is a digit, the token is invalid.

2. Punctuation position check:

   if c in "!.," and i < len(s) - 1:
       return False

   Punctuation marks can only appear at the end of the token. If we find one before the last position, the token is invalid.

3. Hyphen validation:

   if c == "-":
       if (st or 
           i in (0, len(s) - 1) or 
           not s[i - 1].isalpha() or 
           not s[i + 1].isalpha()):
           return False
       st = True

   For a hyphen, we check multiple conditions:

   • st: Has a hyphen already appeared? (only one allowed)
   • i in (0, len(s) - 1): Is it at the beginning or end? (not allowed)
   • not s[i - 1].isalpha(): Is the character before it a letter? (required)
   • not s[i + 1].isalpha(): Is the character after it a letter? (required)

   If all conditions pass, we set st = True to mark that we've seen a hyphen.

Step 4: Count valid words

Finally, we use a generator expression with sum() to count all valid tokens:

return sum(check(s) for s in sentence.split())

The check() function returns True (counted as 1) for valid tokens and False (counted as 0) for invalid ones. The sum gives us the total count of valid words.

Time Complexity: O(n) where n is the length of the sentence, as we traverse each character once.

Space Complexity: O(m) where m is the number of tokens after splitting, needed to store the split results.

Example Walkthrough

Let's walk through the solution with the sentence: "cat and-mice- d0g!"

Step 1: Split into tokens After splitting by spaces, we get: ["cat", "and-mice-", "d0g!"]

Step 2: Validate each token

Token 1: "cat"

• Initialize st = False (no hyphen seen yet)
• Check each character:
  • 'c': Not a digit ✓, not punctuation ✓, not hyphen ✓
  • 'a': Not a digit ✓, not punctuation ✓, not hyphen ✓
  • 't': Not a digit ✓, not punctuation ✓, not hyphen ✓
• Result: Valid (returns True)

Token 2: "and-mice-"

• Initialize st = False
• Check each character:
  • 'a': Not a digit ✓, not punctuation ✓, not hyphen ✓
  • 'n': Not a digit ✓, not punctuation ✓, not hyphen ✓
  • 'd': Not a digit ✓, not punctuation ✓, not hyphen ✓
  • '-' (at index 3):
    • st is False ✓ (first hyphen)
    • Not at position 0 or 8 (last position) ✓
    • s[2] = 'd' is a letter ✓
    • s[4] = 'm' is a letter ✓
    • Set st = True
  • 'm': Not a digit ✓, not punctuation ✓, not hyphen ✓
  • 'i': Not a digit ✓, not punctuation ✓, not hyphen ✓
  • 'c': Not a digit ✓, not punctuation ✓, not hyphen ✓
  • 'e': Not a digit ✓, not punctuation ✓, not hyphen ✓
  • '-' (at index 8):
    • This is at the last position (index 8 = len("and-mice-") - 1)
    • Hyphen at the end is invalid ✗
• Result: Invalid (returns False)

Token 3: "d0g!"

• Initialize st = False
• Check each character:
  • 'd': Not a digit ✓, not punctuation ✓, not hyphen ✓
  • '0': This is a digit ✗
• Result: Invalid (returns False immediately)

Step 3: Count valid words sum([True, False, False]) = sum([1, 0, 0]) = 1

The sentence contains 1 valid word.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the sentence string. This is because:

• The split() method traverses the entire sentence once to split it into words, which takes O(n) time
• For each word generated, the check() function examines each character exactly once
• Since the total number of characters across all words cannot exceed n (the original sentence length), the overall character examination also takes O(n) time
• Therefore, the total time complexity is O(n) + O(n) = O(n)

The space complexity is O(n), where n is the length of the sentence string. This is because:

• The split() method creates a list of words that, in the worst case (sentence with no spaces), could store the entire sentence, requiring O(n) space
• The check() function uses only a constant amount of extra space with variables like st, i, and c, which is O(1)
• Therefore, the total space complexity is dominated by the split operation, resulting in O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Mishandling Empty Tokens

One common pitfall is not considering that split() automatically filters out empty strings when splitting by spaces. However, if you were to use a different splitting method or manual parsing, you might encounter empty strings that could cause index errors.

Example problematic scenario:

# If manually parsing with split(' ') instead of split()
words = sentence.split(' ')  # This keeps empty strings from multiple spaces
# "hello  world" → ['hello', '', 'world']

Solution: Always use split() without arguments, which automatically handles multiple spaces and filters empty strings.

2. Index Out of Bounds When Checking Hyphen

The most critical pitfall is accessing word[index - 1] when index = 0 or word[index + 1] when index = len(word) - 1. The current solution handles this correctly by checking boundary conditions first, but a common mistake is to check the surrounding characters before verifying the position.

Incorrect approach:

if char == "-":
    # WRONG: Checking surrounding chars before boundary check
    if not word[index - 1].isalpha() or not word[index + 1].isalpha():
        return False
    if hyphen_seen or index in (0, len(word) - 1):
        return False

Correct approach (as in solution):

if char == "-":
    # RIGHT: Check boundaries FIRST using short-circuit evaluation
    if (hyphen_seen or 
        index in (0, len(word) - 1) or 
        not word[index - 1].isalpha() or 
        not word[index + 1].isalpha()):
        return False

3. Misunderstanding Punctuation Rules

A subtle pitfall is misinterpreting "at most one punctuation mark" to mean checking for duplicate punctuation marks separately, rather than understanding that the position check inherently enforces this rule.

Overcomplicated approach:

punctuation_count = 0
for char in word:
    if char in "!.,":
        punctuation_count += 1
        if punctuation_count > 1:
            return False

Better approach (as in solution): Since punctuation can only be at the end, checking index < len(word) - 1 automatically ensures at most one punctuation mark exists (multiple punctuation marks would mean at least one is not at the end).

4. Forgetting Edge Cases

Not handling single-character tokens properly, especially:

• Single punctuation mark like "!" or "," (should be valid)
• Single hyphen "-" (should be invalid)
• Single letter "a" (should be valid)

Solution: The current implementation handles these correctly through the logical flow, but it's important to test these edge cases explicitly.