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:
- It contains only lowercase letters, hyphens and punctuation marks — no digits.
- 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). - 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 <= 1000sentence only contains lowercase English letters, digits, ' ', '-', '!', '.' and ','there will be at least 1 token
Hints for Number of Valid Words in a Sentence
Hint 1
Split on spaces and ignore the empty pieces between repeated spaces.
Hint 2
Check each token character by character against the three rules.
Hint 3
A hyphen needs
0 < i < len - 1and letters ati - 1andi + 1; a punctuation mark needsi == 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
- Split
sentenceon spaces, skipping empty tokens. - For each token, scan its characters with a hyphen counter.
- 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.
- A punctuation mark is invalid unless it is the last character.
- 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