Number of Valid Words in a Sentence

Easy
1192.

Number of Valid Words in a Sentence

Number of Valid Words in a Sentence is an easy coding problem on strings and simulation, asked in Amazon and Microsoft interviews.

A sentence is made of lowercase letters, digits, hyphens '-', punctuation marks '!', '.' and ',', and spaces. Splitting it on spaces (one or more) gives its tokens.

A token is a valid word when all three rules hold:

  1. It contains only lowercase letters, hyphens and punctuation marks — no digits.
  2. It contains at most one hyphen, and a hyphen must have a lowercase letter immediately on both sides ("a-b" is fine, "-ab" and "ab-" are not).
  3. It contains at most one punctuation mark, and if there is one it must be the token's last character ("ab,", "cd!" and "." are fine, "a!b" and "c.," are not).

Return the number of valid words in sentence.

Example 1

Input
sentence = "kairo solves bugs-fast!"
Output
3

Example 2

Input
sentence = "a-b-c 4you !no -dash"
Output
0
Explanation
Two hyphens, a digit, punctuation at the start, and a hyphen with no left letter.

Example 3

Input
sentence = "hi, there. ok! x-y, a."
Output
5

Constraints

  • 1 <= sentence.length <= 1000
  • sentence only contains lowercase English letters, digits, ' ', '-', '!', '.' and ','
  • there will be at least 1 token
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} sentence
 * @return {number}
 */
var countValidWords = function(sentence) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Valid Words in a Sentence — Problem & Solution

Number of Valid Words in a Sentence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Number of Valid Words in a Sentence is an easy coding problem on strings and simulation, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Strings, Simulation
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A sentence is made of lowercase letters, digits, hyphens '-', punctuation marks '!', '.' and ',', and spaces. Splitting it on spaces (one or more) gives its tokens.

A token is a valid word when all three rules hold:

  1. It contains only lowercase letters, hyphens and punctuation marks — no digits.
  2. It contains at most one hyphen, and a hyphen must have a lowercase letter immediately on both sides ("a-b" is fine, "-ab" and "ab-" are not).
  3. It contains at most one punctuation mark, and if there is one it must be the token's last character ("ab,", "cd!" and "." are fine, "a!b" and "c.," are not).

Return the number of valid words in sentence.

Example 1

Input: sentence = "kairo  solves bugs-fast!"
Output: 3

Example 2

Input: sentence = "a-b-c 4you !no -dash"
Output: 0
Explanation: Two hyphens, a digit, punctuation at the start, and a hyphen with no left letter.

Example 3

Input: sentence = "hi, there. ok! x-y, a."
Output: 5

Constraints

  • 1 <= sentence.length <= 1000
  • sentence only contains lowercase English letters, digits, ' ', '-', '!', '.' and ','
  • there will be at least 1 token

Hints for Number of Valid Words in a Sentence

  1. Hint 1

    Split on spaces and ignore the empty pieces between repeated spaces.

  2. Hint 2

    Check each token character by character against the three rules.

  3. Hint 3

    A hyphen needs 0 < i < len - 1 and letters at i - 1 and i + 1; a punctuation mark needs i == len - 1; any digit fails the token.

How to solve Number of Valid Words in a Sentence

Validity is a local property of each token, so tokenise and run a single character scan per token that enforces the three rules.

Approach

  1. Split sentence on spaces, skipping empty tokens.
  2. For each token, scan its characters with a hyphen counter.
  3. A digit makes the token invalid. A hyphen is invalid if it is the second one, or sits at either end, or a neighbour is not a lowercase letter.
  4. A punctuation mark is invalid unless it is the last character.
  5. Count the tokens that survive the scan.

Why it works

The scan checks every condition at the exact position it constrains: digits anywhere, each hyphen's neighbours, each punctuation mark's position. Requiring every punctuation mark to be last also limits them to one, and requiring letters on both sides of a hyphen rules out a hyphen next to punctuation. Equivalently, a valid token matches ([a-z]+(-[a-z]+)?)?[!.,]?.

Complexity

  • Time — O(n)
  • Space — O(n) for the tokens (O(1) with an index scan)

Pitfalls

  • Several spaces in a row (and spaces at the ends) produce empty pieces that are not tokens.
  • A lone punctuation mark such as "!" is a valid word.
  • "a-!" is invalid: the hyphen needs a letter on its right.

Reference solution

Python

def countValidWords(sentence: str) -> int:
    def ok(t: str) -> bool:
        n = len(t)
        hy = 0
        for i, c in enumerate(t):
            if '0' <= c <= '9':
                return False
            if c == '-':
                hy += 1
                if hy > 1 or i == 0 or i == n - 1:
                    return False
                if not ('a' <= t[i - 1] <= 'z') or not ('a' <= t[i + 1] <= 'z'):
                    return False
            elif c in '!.,':
                if i != n - 1:
                    return False
        return True
    return sum(1 for t in sentence.split() if ok(t))

Java

static boolean cvwValid(String t) {
    int n = t.length(), hy = 0;
    for (int i = 0; i < n; i++) {
        char c = t.charAt(i);
        if (c >= '0' && c <= '9') return false;
        if (c == '-') {
            hy++;
            if (hy > 1 || i == 0 || i == n - 1) return false;
            if (!Character.isLowerCase(t.charAt(i - 1)) || !Character.isLowerCase(t.charAt(i + 1))) return false;
        } else if (c == '!' || c == '.' || c == ',') {
            if (i != n - 1) return false;
        }
    }
    return true;
}

public static int countValidWords(String sentence) {
    int count = 0;
    for (String t : sentence.split(" ")) {
        if (!t.isEmpty() && cvwValid(t)) count++;
    }
    return count;
}

C++

bool cvwValid(const string& t) {
    int n = t.size(), hy = 0;
    for (int i = 0; i < n; i++) {
        char c = t[i];
        if (c >= '0' && c <= '9') return false;
        if (c == '-') {
            hy++;
            if (hy > 1 || i == 0 || i == n - 1) return false;
            if (!(t[i - 1] >= 'a' && t[i - 1] <= 'z') || !(t[i + 1] >= 'a' && t[i + 1] <= 'z')) return false;
        } else if (c == '!' || c == '.' || c == ',') {
            if (i != n - 1) return false;
        }
    }
    return true;
}

int countValidWords(string sentence) {
    istringstream in1(sentence);
    string t;
    int count = 0;
    while (in1 >> t) if (cvwValid(t)) count++;
    return count;
}

JavaScript

var countValidWords = function(sentence) {
    var isLower = function(c) { return c >= "a" && c <= "z"; };
    var toks = sentence.split(" ");
    var count = 0;
    for (var k = 0; k < toks.length; k++) {
        var t = toks[k];
        if (t.length === 0) continue;
        var ok = true, hy = 0;
        for (var i = 0; i < t.length && ok; i++) {
            var c = t[i];
            if (c >= "0" && c <= "9") ok = false;
            else if (c === "-") {
                hy++;
                if (hy > 1 || i === 0 || i === t.length - 1 || !isLower(t[i - 1]) || !isLower(t[i + 1])) ok = false;
            } else if (c === "!" || c === "." || c === ",") {
                if (i !== t.length - 1) ok = false;
            }
        }
        if (ok) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings