Number of Valid Words in a Sentence - Practice Coding Problems

Number of Valid Words in a Sentence - Problem

String Easy

A sentence consists of lowercase letters ('a' to 'z'), digits ('0' to '9'), hyphens ('-'), punctuation marks ('!', '.', and ','), and spaces (' ') only. Each sentence can be broken down into one or more tokens separated by one or more spaces ' '.

A token is a valid word if all three of the following are true:

It only contains lowercase letters, hyphens, and/or punctuation (no digits).
There is at most one hyphen '-'. If present, it must be surrounded by lowercase characters ("a-b" is valid, but "-ab" and "ab-" are not valid).
There is at most one punctuation mark. If present, it must be at the end of the token ("ab,", "cd!", and "." are valid, but "a!b" and "c.," are not valid).

Examples of valid words include "a-b.", "afad", "ba-c", "a!", and "!".

Given a string sentence, return the number of valid words in sentence.

Input & Output

Example 1 — Basic Validation

$ Input: sentence = "cat and dog"

› Output: 3

💡 Note: All three words are valid: "cat" (only lowercase), "and" (only lowercase), "dog" (only lowercase). Multiple spaces between words don't affect token validation.

Example 2 — Invalid Words with Digits

$ Input: sentence = "!this 1-s b8d!"

› Output: 2

💡 Note: "!this" is valid (punctuation at start, only letters after), "1-s" is invalid (contains digit), "b8d!" is invalid (contains digit). Only 2 valid words.

Example 3 — Hyphen and Punctuation Rules

$ Input: sentence = "alice and bob are playing stone-game10"

› Output: 5

💡 Note: "alice", "and", "bob", "are", "playing" are all valid. "stone-game10" is invalid due to digits. Hyphen in "stone-game10" would be valid if no digits were present.

Constraints

1 ≤ sentence.length ≤ 1000
sentence only contains lowercase English letters, digits, spaces, hyphens, and punctuation marks

Visualization

Tap to expand

Understanding the Visualization

Input

Sentence with mixed valid/invalid tokens

Validation

Check each token against three rules

Count

Count tokens that pass all rules

Key Takeaway

🎯 Key Insight: A token is valid only if it passes ALL three checks: no digits, proper hyphen placement, proper punctuation placement

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that each token must satisfy exactly three validation rules: no digits, at most one properly-placed hyphen, and at most one punctuation mark at the end. Best approach is single pass scanning for optimal space efficiency. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Character Scanning	O(n)	O(1)	Process sentence character by character, validating tokens on the fly
Brute Force Split and Validate	O(n)	O(n)	Split sentence into tokens, then check each token against all validation rules

Single Pass Character Scanning — Algorithm Steps

Step 1: Scan sentence character by character
Step 2: Build current token while tracking validation state
Step 3: When space encountered, validate current token and reset

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan

Move through sentence character by character

Build

Build current token until space encountered

Validate

Validate completed token immediately

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int isValidToken(char* token) {
    int len = strlen(token);
    if (len == 0) return 0;
    
    int hyphenCount = 0;
    int punctuationCount = 0;
    
    for (int i = 0; i < len; i++) {
        char ch = token[i];
        if (isdigit(ch)) {
            return 0;
        } else if (ch == '-') {
            hyphenCount++;
            if (hyphenCount > 1) return 0;
            if (i == 0 || i == len - 1 || 
                !islower(token[i-1]) || !islower(token[i+1])) {
                return 0;
            }
        } else if (ch == '!' || ch == '.' || ch == ',') {
            punctuationCount++;
            if (punctuationCount > 1 || i != len - 1) {
                return 0;
            }
        } else if (!islower(ch)) {
            return 0;
        }
    }
    
    return 1;
}

int solution(char* sentence) {
    int validCount = 0;
    char currentToken[1001];
    int tokenLen = 0;
    
    for (int i = 0; sentence[i]; i++) {
        if (sentence[i] == ' ') {
            if (tokenLen > 0) {
                currentToken[tokenLen] = '\0';
                if (isValidToken(currentToken)) {
                    validCount++;
                }
                tokenLen = 0;
            }
        } else {
            currentToken[tokenLen++] = sentence[i];
        }
    }
    
    // Check the last token
    if (tokenLen > 0) {
        currentToken[tokenLen] = '\0';
        if (isValidToken(currentToken)) {
            validCount++;
        }
    }
    
    return validCount;
}

int main() {
    char sentence[10001];
    fgets(sentence, sizeof(sentence), stdin);
    sentence[strcspn(sentence, "\n")] = 0;
    
    int result = solution(sentence);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the sentence with constant work per character

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track current token state, no token storage

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Character Scanning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler