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:
'a' to 'z'),'-') only if each hyphen is surrounded by lowercase English letters, andAny 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:
chunks gives s = "hello world hello".s are "hello" which appears twice and "world" which appears once.ans = [2, 1, 0].Example 2:
Input: chunks = ["a--b a-","-c"], queries = ["a","b","c"]
Output: [2,1,1]
Explanation:
chunks gives s = "a--b a--c".s are "a" which appears twice, "b" which appears once, and "c" which appears once.ans = [2, 1, 1].Example 3:
Input: chunks = ["hello"], queries = ["hello","ell"]
Output: [1,0]
Explanation:
s is "hello" which appears once.ans = [1, 0].
Constraints:
1 <= chunks.length <= 1051 <= chunks[i].length <= 105chunks[i] may consist of lowercase English letters, spaces, and hyphens.chunks does not exceed 1051 <= queries.length <= 1051 <= queries[i].length <= 105queries[i] is a valid wordqueries does not exceed 105Problem 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.
Solutions for this problem are being prepared.
Try solving it yourself| 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 |
Practice Count Valid Word Occurrences with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor