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.

Description Solution Video 40:51

3926. Count Valid Word Occurrences

Medium48.1% acceptance

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 chunks gives s = "hello world hello".
The valid words in s are "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 chunks gives s = "a--b a--c".
The valid words in s are "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 s is "hello" which appears once.
Thus, the ans = [1, 0].

Constraints:

1 <= chunks.length <= 10⁵
1 <= chunks[i].length <= 10⁵
chunks[i] may consist of lowercase English letters, spaces, and hyphens.
The total length of all strings in chunks does not exceed 10⁵
1 <= queries.length <= 10⁵
1 <= queries[i].length <= 10⁵
queries[i] is a valid word
The total length of all strings in queries does not exceed 10⁵

Topics

40:51

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def countWordOccurrences(self, chunks: list[str], queries: list[str]) -> list[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

["hello wor","ld hello"]
["hello","world","wor"]

Input

["a--b a-","-c"]
["a","b","c"]

Input

["hello"]
["hello","ell"]

Your code is saved on this device.Solution