Skip to main content
Talentd

Count Valid Word Occurrences - Solution & Explanation

MediumArrayHash TableStringCounting9 min read
Practice this problem

Problem Statement

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 <= 105
  • 1 <= chunks[i].length <= 105ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹
  • chunks[i] may consist of lowercase English letters, spaces, and hyphens.
  • The total length of all strings in chunks does not exceed 105
  • 1 <= queries.length <= 105
  • 1 <= queries[i].length <= 105ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹
  • queries[i] is a valid word
  • The total length of all strings in queries does not exceed 105

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Substring Boundary CheckO(n * m)O(1)Useful when demonstrating the direct brute-force idea without extra memory
Split and Compare TokensO(n)O(n)Best for readability using built-in string utilities
Single Pass String ScanO(n)O(1)Optimal approach when minimizing extra memory

Video Solution

weekly contest 501| leetcode 3925 | leetcode 3926| leetcode 3927| leetcode 3928| Dijkstra| DSA ā€¢ Code With Vick ā€¢ 558 views views

Watch 4 more video solutions ā†’

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.

Ready to solve this problem?

Practice Count Valid Word Occurrences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays