Count Valid Word Occurrences solution and explanation
4 more videos on this problem
weekly contest 501| leetcode 3925 | leetcode 3926| leetcode 3927| leetcode 3928| Dijkstra| DSACode With Vick · 40:51 · 558 views
Count Valid Word Occurrences | LeetCode 3926 | Weekly Contest 501 | Java | Developer CoderDeveloper Coder · 10:03 · 379 views
Count Valid Word Occurrences | Leetcode weekly contest 501 | #3926UMANG AGRAWAL · 11:26 · 236 views
Leetcode 3926. Count Valid Word Occurrences | O(NLogN) | MediumLeet's Code · 19:46 · 182 views
LeetCode Weekly Contest 501 | Q2 Count Valid Word Occurrences | Full IntuitionDesiCoding · 10:26 · 103 views
The problem
You are given an array of strings chunks. The strings are concatenated in order to form a single string s.
You are also given an array of strings queries.
A word is defined as a substring of s that:
- consists of lowercase English letters (
'a'to'z'), - may include hyphens (
'-') only if each hyphen is surrounded by lowercase English letters, and - is not part of a longer substring that also satisfies the above conditions.
Any character that is not a lowercase English letter or a valid hyphen acts as a separator.
Return an integer array ans such that ans[i] is the number of occurrences of queries[i] as a word in s.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: chunks = ["hello wor","ld hello"], queries = ["hello","world","wor"]
Output: [2,1,0]
Explanation:
- Concatenating all strings in
chunksgivess = "hello world hello". - The valid words in
sare"hello"which appears twice and"world"which appears once. - Thus, the
ans = [2, 1, 0].
Example 2:
Input: chunks = ["a--b a-","-c"], queries = ["a","b","c"]
Output: [2,1,1]
Explanation:
- Concatenating all strings in
chunksgivess = "a--b a--c". - The valid words in
sare"a"which appears twice,"b"which appears once, and"c"which appears once. - Thus, the
ans = [2, 1, 1].
Example 3:
Input: chunks = ["hello"], queries = ["hello","ell"]
Output: [1,0]
Explanation:
- The valid word in
sis"hello"which appears once. - Thus, the
ans = [1, 0].
Constraints:
1 <= chunks.length <= 1051 <= chunks[i].length <= 105chunks[i]may consist of lowercase English letters, spaces, and hyphens.- The total length of all strings in
chunksdoes not exceed105 1 <= queries.length <= 1051 <= queries[i].length <= 105queries[i]is a valid word- The total length of all strings in
queriesdoes not exceed105
Approach overview
Problem Overview: Given a sentence and a target word, count how many times the word appears as a valid standalone token. Substrings inside other words should not count. The core task is parsing the sentence correctly and verifying exact word matches.
Approach 1: Brute Force Substring Checking (O(n * m) time, O(1) space)
A straightforward method scans every index of the sentence and checks whether the substring starting at that position equals the target word. For each match attempt, verify the boundaries: the character before the word must be a space or start of string, and the character after must be a space or end of string. This ensures the match represents a full word rather than part of another token. The approach uses repeated substring comparisons, giving O(n * m) time where n is sentence length and m is word length. No additional data structures are required, so space complexity stays O(1).
Approach 2: Split and Compare Tokens (O(n) time, O(n) space)
A cleaner solution splits the sentence into tokens using spaces. Each token becomes a candidate word, so you simply iterate through the resulting array and compare it with the target word. Each comparison is constant time relative to token length, making the total complexity O(n). The tradeoff is memory usage: splitting creates an array of tokens, which requires O(n) extra space. This approach is common in interviews because it is readable and leverages built-in string utilities.
Approach 3: Single Pass String Scan (O(n) time, O(1) space)
The optimal approach scans the sentence once while building words character by character. Whenever a space is encountered, the accumulated word is compared with the target. If it matches, increment the count and reset the buffer for the next word. After the loop, check the final token as well. This method avoids allocating arrays or using heavy string operations, so it maintains O(n) time with constant O(1) extra space. It relies purely on character iteration, a pattern frequently used in string processing problems.
Recommended for interviews: Start by explaining the brute force boundary-check idea to demonstrate understanding of word matching. Then move to the single-pass scan solution. Interviewers typically expect an O(n) string traversal with constant space, showing comfort with low-level string parsing and basic array-style iteration patterns.
Solution
First, we concatenate all strings in chunks to obtain a single string s.
Since the first character of a valid word must be a lowercase English letter, we scan s from left to right. When we encounter a lowercase English letter, we continue scanning to the right. If we encounter a space or an invalid hyphen, it means we have found a word. We add this word to a hash table and count its occurrences. Finally, we iterate through each string in queries, look up its count in the hash table, and append the result to the answer array.
The time complexity is O(n + m), where n is the total length of all strings in chunks, and m is the total length of all strings in queries.
class Solution:
def countWordOccurrences(self, chunks: list[str], queries: list[str]) -> list[int]:
s = "".join(chunks)
n = len(s)
cnt = defaultdict(int)
i = 0
while i < n:
if s[i] in " -":
i += 1
continue
j = i
while (
j < n
and s[j] != " "
and (s[j] != "-" or (j + 1 < n and s[j + 1] not in " -"))
):
j += 1
cnt[s[i:j]] += 1
i = j
return [cnt[q] for q in queries]class Solution {
public int[] countWordOccurrences(String[] chunks, String[] queries) {
StringBuilder sb = new StringBuilder();
for (String chunk : chunks) {
sb.append(chunk);
}
String s = sb.toString();
int n = s.length();
Map<String, Integer> cnt = new HashMap<>();
int i = 0;
while (i < n) {
char c = s.charAt(i);
if (c == ' ' || c == '-') {
i++;
continue;
}
int j = i;
while (j < n) {
char cj = s.charAt(j);
if (cj == ' ') {
break;
}
if (cj == '-') {
if (j + 1 < n) {
char cnext = s.charAt(j + 1);
if (cnext == ' ' || cnext == '-') {
break;
}
} else {
break;
}
}
j++;
}
String word = s.substring(i, j);
cnt.put(word, cnt.getOrDefault(word, 0) + 1);
i = j;
}
int[] ans = new int[queries.length];
for (int k = 0; k < queries.length; k++) {
ans[k] = cnt.getOrDefault(queries[k], 0);
}
return ans;
}
}class Solution {
public:
vector<int> countWordOccurrences(vector<string>& chunks, vector<string>& queries) {
string s = "";
for (const string& chunk : chunks) {
s += chunk;
}
int n = s.length();
unordered_map<string, int> cnt;
int i = 0;
while (i < n) {
if (s[i] == ' ' || s[i] == '-') {
i++;
continue;
}
int j = i;
while (j < n && s[j] != ' ' && (s[j] != '-' || (j + 1 < n && s[j + 1] != ' ' && s[j + 1] != '-'))) {
j++;
}
cnt[s.substr(i, j - i)]++;
i = j;
}
vector<int> ans;
ans.reserve(queries.size());
for (const string& q : queries) {
ans.push_back(cnt[q]);
}
return ans;
}
};function countWordOccurrences(chunks: string[], queries: string[]): number[] {
const s = chunks.join('');
const n = s.length;
const cnt = new Map<string, number>();
let i = 0;
while (i < n) {
if (s[i] === ' ' || s[i] === '-') {
i++;
continue;
}
let j = i;
while (
j < n &&
s[j] !== ' ' &&
(s[j] !== '-' || (j + 1 < n && s[j + 1] !== ' ' && s[j + 1] !== '-'))
) {
j++;
}
const word = s.substring(i, j);
cnt.set(word, (cnt.get(word) || 0) + 1);
i = j;
}
return queries.map(q => cnt.get(q) || 0);
}func countWordOccurrences(chunks []string, queries []string) []int {
s := strings.Join(chunks, "")
n := len(s)
cnt := make(map[string]int)
i := 0
for i < n {
if s[i] == ' ' || s[i] == '-' {
i++
continue
}
j := i
for j < n && s[j] != ' ' && (s[j] != '-' || (j+1 < n && s[j+1] != ' ' && s[j+1] != '-')) {
j++
}
cnt[s[i:j]]++
i = j
}
ans := make([]int, len(queries))
for k, q := range queries {
ans[k] = cnt[q]
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Substring Boundary Check | O(n * m) | O(1) | Useful when demonstrating the direct brute-force idea without extra memory |
| Split and Compare Tokens | O(n) | O(n) | Best for readability using built-in string utilities |
| Single Pass String Scan | O(n) | O(1) | Optimal approach when minimizing extra memory |
Frequently asked questions
Is Count Valid Word Occurrences easy or hard?
The problem is generally considered medium difficulty because it tests careful string parsing and edge cases such as boundaries, spacing, and exact word matching rather than simple substring checks.
Count Valid Word Occurrences Python/Java solution
Both Python and Java solutions typically iterate through the sentence and compare tokens with the target word. Python often uses split() for simplicity, while Java solutions may use split() or manual character iteration for better space efficiency.
How to solve Count Valid Word Occurrences in O(n)?
Traverse the sentence once while constructing the current word. When a space is encountered, compare the built token with the target word and increment the counter if they match. Reset the buffer and continue scanning until the end of the string.
What is the best approach for Count Valid Word Occurrences?
The best approach is a single-pass string scan. Iterate through the sentence character by character, build each word, and compare it with the target when a space or end of string appears. This method runs in O(n) time and uses O(1) extra space.
Is Count Valid Word Occurrences asked at Google/Amazon/Meta?
Word parsing and string tokenization problems frequently appear in interviews at companies like Amazon and Google. Variants often test string traversal, boundary handling, and efficient scanning techniques.
What data structure is used in Count Valid Word Occurrences?
The problem mainly relies on string traversal. Some solutions use arrays created by splitting the sentence into tokens, while optimal implementations simply track characters in a running buffer without additional data structures.
What is the time complexity of Count Valid Word Occurrences?
The optimal solution runs in O(n) time where n is the length of the sentence. Each character is processed once during the scan. Space complexity can be O(1) with manual parsing or O(n) if the sentence is split into tokens.