3926. Count Valid Word Occurrences
Problem Description
You are given an array of strings chunks. Concatenate all strings in chunks in order to form a single string s.
You are also given an array of strings queries.
Some definitions to keep in mind:
-
A joiner hyphen is a hyphen character
'-'inswhose previous and next characters both exist and are lowercase English letters. In other words, a hyphen only counts as a joiner if it sits directly between two lowercase letters (for example, in"co-op", the hyphen is a joiner hyphen). -
A word is a maximal substring of
smade up of only lowercase English letters and joiner hyphens. "Maximal" means the substring cannot be extended further to the left or right while still satisfying this condition. -
All other characters—including spaces and any hyphens that are not joiner hyphens—are treated as separators that break words apart.
Your task is to return an integer array ans, where ans[i] is the number of times queries[i] appears as a word in s.
For example, if s = "co-op shop -hat", then:
"co-op"is a word because the hyphen is between two lowercase letters."shop"is a word.- In
"-hat", the leading hyphen has no valid previous character, so it is treated as a separator, and only"hat"is the word.
So if queries = ["co-op", "shop", "hat", "co"], the answer would be [1, 1, 1, 0], since "co" never appears as a standalone word.
How We Pick the Algorithm
Why Greedy Algorithms?
This problem maps to Greedy Algorithms through a short path in the full flowchart.
Making the locally optimal choice at each step produces the globally optimal result.
Open in FlowchartIntuition
The key observation is that every valid word must start with a lowercase English letter. A word can never begin with a hyphen, because a joiner hyphen requires a lowercase letter on both sides—so a hyphen sitting at the start of a potential word would have no valid previous character and would therefore act as a separator instead.
This insight lets us scan the string s from left to right and split it into words naturally:
- If the current character is a separator (a space, or a hyphen that is not a joiner), we skip it.
- If the current character is a lowercase letter, we have found the start of a word. We keep extending to the right as long as the next character is either another lowercase letter or a joiner hyphen.
The tricky part is deciding when a hyphen continues the word versus when it ends it. A hyphen at position j is a joiner only if the character s[j + 1] exists and is a lowercase letter (we already know s[j - 1] is a letter because we only reach a hyphen after consuming a letter). So when we hit a hyphen whose next character is a space or another hyphen, the word stops right before that hyphen.
Once we extract each word using this rule, the problem reduces to simple counting. We store the frequency of every word in a hash table. Then, for each string in queries, we just look up how many times it occurred. This avoids re-scanning the string for every query and gives us the answer efficiently in a single pass over s plus one lookup per query.
Solution Approach
We use a single linear scan combined with a hash table for counting.
Step 1: Build the string.
First, we concatenate all strings in chunks to obtain the full string s, and record its length n.
s = "".join(chunks)
n = len(s)
Step 2: Set up the counter.
We use a hash table cnt (a defaultdict(int)) to store how many times each word appears.
cnt = defaultdict(int)
Step 3: Scan and extract words.
We use a pointer i to walk through s from left to right:
- If
s[i]is a separator (a space or a hyphen, since a word can never begin with a hyphen), we skip it by movingiforward by one.
if s[i] in " -": i += 1 continue
- Otherwise,
s[i]is a lowercase letter, marking the start of a word. We use a second pointerjstarting atito find where the word ends. We keep advancingjwhile all of the following hold:j < n(we stay within bounds),s[j] != " "(we have not hit a space separator),s[j]is not a hyphen, or it is a hyphen that qualifies as a joiner hyphen, meaning the next characters[j + 1]exists and is not a space or hyphen (s[j + 1] not in " -").
j = i while ( j < n and s[j] != " " and (s[j] != "-" or (j + 1 < n and s[j + 1] not in " -")) ): j += 1
Notice we only need to check s[j + 1] for the hyphen condition. We already know s[j - 1] is a valid letter because we reached this hyphen only after consuming a letter, so the "previous character" requirement is automatically satisfied.
Step 4: Record the word.
The substring s[i:j] is one complete word. We increment its count in the hash table, then move i to j to continue scanning from where the word ended.
cnt[s[i:j]] += 1 i = j
Step 5: Answer the queries.
After the scan, every word and its frequency are stored in cnt. For each string in queries, we simply look it up. If a query never appeared, the defaultdict returns 0.
return [cnt[q] for q in queries]
Complexity Analysis:
- Time Complexity:
O(n + L + q), wherenis the length ofs,Lis the total length of all query strings (for the lookups and hashing), andqis the number of queries. The scan oversvisits each character a constant number of times. - Space Complexity:
O(n)for storing the stringsand the words in the hash table.
Example Walkthrough
Let's trace through a small example to see how the solution approach works step by step.
Input:
chunks = ["co-o", "p sh", "op -h", "at"]queries = ["co-op", "shop", "hat", "co"]
Step 1: Build the string.
Concatenating all chunks in order:
"co-o" + "p sh" + "op -h" + "at" = "co-op shop -hat"
So s = "co-op shop -hat" and n = 15. Let's index it for reference:
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Char: c o - o p s h o p - h a t
Step 2: Set up the counter.
We start with an empty hash table: cnt = {}.
Step 3 & 4: Scan and extract words.
We walk through s with pointer i:
-
i = 0('c') — a lowercase letter, so a word begins. We advancej:j=0'c': letter → continuej=1'o': letter → continuej=2'-': hyphen, checks[3] = 'o'which is not in" -"→ joiner, continuej=3'o': letter → continuej=4'p': letter → continuej=5' ': space → stop
Word extracted is
s[0:5] = "co-op". Updatecnt["co-op"] = 1. Movei = 5. -
i = 5(' ') — a separator, skip. Movei = 6. -
i = 6('s') — a lowercase letter, word begins. We advancej:j=6's',j=7'h',j=8'o',j=9'p': all letters → continuej=10' ': space → stop
Word extracted is
s[6:10] = "shop". Updatecnt["shop"] = 1. Movei = 10. -
i = 10(' ') — a separator, skip. Movei = 11. -
i = 11('-') — a hyphen is treated as a separator at the start (a word can never begin with a hyphen), skip. Movei = 12. -
i = 12('h') — a lowercase letter, word begins. We advancej:j=12'h',j=13'a',j=14't': all letters → continuej=15: out of bounds → stop
Word extracted is
s[12:15] = "hat". Updatecnt["hat"] = 1. Movei = 15. -
i = 15— reached the end. Scan complete.
The final hash table is:
cnt = {"co-op": 1, "shop": 1, "hat": 1}
Notice that the leading hyphen in "-hat" was skipped as a separator, so only "hat" was recorded—exactly as expected.
Step 5: Answer the queries.
We look up each query in cnt:
| Query | Lookup in cnt | Result |
|---|---|---|
"co-op" | found, count 1 | 1 |
"shop" | found, count 1 | 1 |
"hat" | found, count 1 | 1 |
"co" | not found | 0 |
The query "co" returns 0 because "co" never appeared as a standalone word—it was always part of "co-op".
Output: [1, 1, 1, 0]
This matches the expected answer, confirming the single-pass scan correctly identifies joiner hyphens and the hash table efficiently answers all queries.
Solution Implementation
1from collections import defaultdict
2
3
4class Solution:
5 def countWordOccurrences(self, chunks: list[str], queries: list[str]) -> list[int]:
6 # Combine all chunks into a single continuous string
7 text = "".join(chunks)
8 length = len(text)
9
10 # Map each extracted word to its occurrence count
11 word_count: dict[str, int] = defaultdict(int)
12
13 index = 0
14 while index < length:
15 # Skip standalone separators (spaces, or hyphens used as delimiters)
16 if text[index] in " -":
17 index += 1
18 continue
19
20 # Mark the start of the current word
21 start = index
22 while (
23 index < length
24 # Stop at a space (always a word boundary)
25 and text[index] != " "
26 # A hyphen ends the word only when it is NOT an internal hyphen,
27 # i.e. when it is the last char or followed by a space/hyphen.
28 # It stays inside the word when followed by a normal character
29 # (e.g. "well-known").
30 and (
31 text[index] != "-"
32 or (index + 1 < length and text[index + 1] not in " -")
33 )
34 ):
35 index += 1
36
37 # Record the word spanning [start, index)
38 word_count[text[start:index]] += 1
39 index = index
40
41 # Answer each query with the precomputed count (0 if unseen)
42 return [word_count[query] for query in queries]
43```
44
45**Notes on the changes:**
46
471. **Standardized naming:** `s` → `text`, `n` → `length`, `cnt` → `word_count`, `i` → `index`, `j` → `start`/loop index. The method name `countWordOccurrences` was preserved as required.
48
492. **Added the missing import** (`from collections import defaultdict`), since the original relied on it but didn't include it.
50
513. **Type hint** added for `word_count` for clarity.
52
53One small thing worth flagging: in my rewrite I merged the original two pointers (`i` and `j`) into a single advancing `index`, which makes the line `index = index` redundant. A cleaner version keeps two pointers:
54
55```python3
56from collections import defaultdict
57
58
59class Solution:
60 def countWordOccurrences(self, chunks: list[str], queries: list[str]) -> list[int]:
61 # Combine all chunks into a single continuous string
62 text = "".join(chunks)
63 length = len(text)
64
65 # Map each extracted word to its occurrence count
66 word_count: dict[str, int] = defaultdict(int)
67
68 start = 0
69 while start < length:
70 # Skip separators: spaces and delimiter hyphens
71 if text[start] in " -":
72 start += 1
73 continue
74
75 # Extend `end` to cover the full word
76 end = start
77 while (
78 end < length
79 and text[end] != " "
80 and (
81 text[end] != "-"
82 or (end + 1 < length and text[end + 1] not in " -")
83 )
84 ):
85 end += 1
86
87 # Count the word in [start, end)
88 word_count[text[start:end]] += 1
89 start = end
90
91 return [word_count[query] for query in queries]
921class Solution {
2 /**
3 * Counts the occurrences of each queried word within the text formed
4 * by concatenating all the given chunks.
5 *
6 * Word boundaries are defined by spaces. A hyphen '-' is treated as part
7 * of a word only when it sits between two non-space, non-hyphen characters
8 * (i.e. a true intra-word hyphen). Otherwise it acts as a separator.
9 *
10 * @param chunks the pieces of text to be concatenated into a single string
11 * @param queries the words whose occurrences need to be counted
12 * @return an array where each element is the count of the corresponding query word
13 */
14 public int[] countWordOccurrences(String[] chunks, String[] queries) {
15 // Concatenate all chunks into one continuous string.
16 StringBuilder builder = new StringBuilder();
17 for (String chunk : chunks) {
18 builder.append(chunk);
19 }
20 String text = builder.toString();
21 int length = text.length();
22
23 // Map to store how many times each extracted word appears.
24 Map<String, Integer> wordCount = new HashMap<>();
25
26 int index = 0;
27 while (index < length) {
28 char current = text.charAt(index);
29
30 // Skip leading separators (spaces or hyphens that start a token).
31 if (current == ' ' || current == '-') {
32 index++;
33 continue;
34 }
35
36 // Scan forward to find the end of the current word.
37 int end = index;
38 while (end < length) {
39 char ch = text.charAt(end);
40
41 // A space always ends the current word.
42 if (ch == ' ') {
43 break;
44 }
45
46 // A hyphen ends the word unless it is a genuine intra-word hyphen,
47 // meaning the next character is also a normal word character.
48 if (ch == '-') {
49 if (end + 1 < length) {
50 char next = text.charAt(end + 1);
51 if (next == ' ' || next == '-') {
52 break;
53 }
54 } else {
55 // Trailing hyphen at the very end: treat as separator.
56 break;
57 }
58 }
59
60 end++;
61 }
62
63 // Extract the word and update its count.
64 String word = text.substring(index, end);
65 wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
66
67 // Move to the position right after the current word.
68 index = end;
69 }
70
71 // Build the answer array based on the query words.
72 int[] answer = new int[queries.length];
73 for (int k = 0; k < queries.length; k++) {
74 answer[k] = wordCount.getOrDefault(queries[k], 0);
75 }
76 return answer;
77 }
78}
791class Solution {
2public:
3 vector<int> countWordOccurrences(vector<string>& chunks, vector<string>& queries) {
4 // Concatenate all chunks into a single string for unified processing.
5 string text;
6 for (const string& chunk : chunks) {
7 text += chunk;
8 }
9
10 int length = static_cast<int>(text.length());
11
12 // Map each distinct word to the number of times it appears.
13 unordered_map<string, int> wordCount;
14
15 int start = 0;
16 while (start < length) {
17 // Skip separators (spaces and standalone hyphens).
18 if (text[start] == ' ' || text[start] == '-') {
19 start++;
20 continue;
21 }
22
23 // Advance 'end' to find the boundary of the current word.
24 // A space always ends a word. A hyphen ends the word only when it
25 // is NOT acting as an in-word connector, i.e. it is immediately
26 // followed by another separator (or the end of the string).
27 int end = start;
28 while (end < length && text[end] != ' ' &&
29 (text[end] != '-' ||
30 (end + 1 < length && text[end + 1] != ' ' && text[end + 1] != '-'))) {
31 end++;
32 }
33
34 // Record the extracted word [start, end).
35 wordCount[text.substr(start, end - start)]++;
36
37 // Continue scanning from where the current word ended.
38 start = end;
39 }
40
41 // Resolve each query against the precomputed counts.
42 vector<int> answer;
43 answer.reserve(queries.size());
44 for (const string& query : queries) {
45 answer.push_back(wordCount[query]);
46 }
47
48 return answer;
49 }
50};
511/**
2 * Counts the number of occurrences of each query word within the joined text.
3 *
4 * Words are delimited by spaces (' ') and standalone hyphens ('-').
5 * A hyphen that sits between two non-space, non-hyphen characters is treated
6 * as part of the word (e.g. "well-known" stays intact), whereas a hyphen
7 * adjacent to a space or another hyphen acts as a separator.
8 *
9 * @param chunks - Array of string fragments that together form the full text.
10 * @param queries - Array of words whose occurrences we want to count.
11 * @returns An array where each element is the count for the corresponding query.
12 */
13function countWordOccurrences(chunks: string[], queries: string[]): number[] {
14 // Combine all fragments into a single continuous string.
15 const text: string = chunks.join('');
16 const length: number = text.length;
17
18 // Map from a word to the number of times it appears in the text.
19 const wordCount: Map<string, number> = new Map<string, number>();
20
21 let start: number = 0;
22 while (start < length) {
23 // Skip leading separators (spaces and standalone hyphens).
24 if (text[start] === ' ' || text[start] === '-') {
25 start++;
26 continue;
27 }
28
29 // Expand the window [start, end) to capture a full word.
30 let end: number = start;
31 while (
32 end < length &&
33 text[end] !== ' ' &&
34 // A hyphen is part of the word only when the next character
35 // is neither a space nor another hyphen (i.e. it is an inner hyphen).
36 (text[end] !== '-' ||
37 (end + 1 < length &&
38 text[end + 1] !== ' ' &&
39 text[end + 1] !== '-'))
40 ) {
41 end++;
42 }
43
44 // Extract the word and increment its tally.
45 const word: string = text.substring(start, end);
46 wordCount.set(word, (wordCount.get(word) ?? 0) + 1);
47
48 // Continue scanning from the end of the current word.
49 start = end;
50 }
51
52 // Resolve each query to its stored count, defaulting to 0 when absent.
53 return queries.map((query: string): number => wordCount.get(query) ?? 0);
54}
55Time and Space Complexity
Time Complexity: O(n + m)
The analysis proceeds in several stages:
-
Joining the chunks: The operation
"".join(chunks)concatenates all strings inchunks, producing a stringsof lengthn, wherenis the total length of all strings inchunks. This takesO(n)time. -
Scanning the string: The
whileloop traversessusing two pointersiandj. Although there is a nested inner loop, each character ofsis visited a constant number of times overall — the pointeriis only ever advanced toj, andjonly moves forward. Thus the entire scan, including the slicings[i:j]to extract words and thedefaultdictinsertions, costsO(n)in aggregate. -
Answering the queries: The final list comprehension
[cnt[q] for q in queries]performs one hash lookup per query. Each lookup of a queryqcosts time proportional to the length ofq, so summing over all queries givesO(m), wheremis the total length of all strings inqueries.
Combining these stages yields a total time complexity of O(n + m).
Space Complexity: O(n)
The space usage is dominated by:
- The concatenated string
s, which occupiesO(n)space. - The
cntdictionary, which stores the distinct words extracted fromsalong with their counts. In the worst case, the total size of all stored keys is bounded by the length ofs, i.e.,O(n).
The output list contributes O(len(queries)) space, which is not larger than O(m). Considering the auxiliary space required by the algorithm, the overall space complexity is O(n).
Common Pitfalls
Pitfall: Mishandling the joiner-hyphen boundary conditions
The single most error-prone part of this problem is correctly deciding when a hyphen is a joiner (stays inside a word) versus a separator (breaks words apart). A joiner hyphen requires both neighbors to be lowercase letters. A naive implementation often gets one of the two boundary checks wrong, producing incorrect word splits.
There are three classic mistakes:
1. Forgetting the leading-hyphen case (no valid previous character).
If you start scanning a word at a hyphen, the "previous character" requirement is silently violated. In the reference solution, this is handled by treating any hyphen at the start position as a separator:
if text[start] in " -": # a hyphen here can never be a joiner start += 1 continue
If you instead only skip spaces here (if text[start] == " "), then a string like "-hat" would incorrectly start a word at the leading -, yielding the word "-hat" instead of "hat".
2. Forgetting the trailing-hyphen / consecutive-hyphen case (no valid next character).
Inside the inner loop, a hyphen must be followed by a lowercase letter to remain a joiner. If you forget to check text[end + 1], you might wrongly absorb a trailing hyphen, turning "hat-" into the word "hat-", or merge across a double hyphen "a--b" into one chunk.
and ( text[end] != "-" or (end + 1 < length and text[end + 1] not in " -") # next must exist & be a letter )
3. Out-of-bounds access when checking the next character.
Writing text[end + 1] not in " -" without first guarding end + 1 < length throws an IndexError when a hyphen is the very last character of text. The short-circuit ordering matters:
# CORRECT: bounds check first, short-circuits before indexing (end + 1 < length and text[end + 1] not in " -") # WRONG: indexes text[end + 1] even when end is the last index (text[end + 1] not in " -" and end + 1 < length)
A robust, self-documenting fix
To avoid all three traps at once, factor the joiner test into a single helper so the boundary logic lives in exactly one place and reads exactly like the problem statement ("previous and next are lowercase letters"):
from collections import defaultdict
class Solution:
def countWordOccurrences(self, chunks: list[str], queries: list[str]) -> list[int]:
text = "".join(chunks)
length = len(text)
def is_letter(idx: int) -> bool:
return 0 <= idx < length and text[idx].islower()
def is_joiner(idx: int) -> bool:
# A hyphen is a joiner only if BOTH neighbors are lowercase letters.
return text[idx] == "-" and is_letter(idx - 1) and is_letter(idx + 1)
word_count: dict[str, int] = defaultdict(int)
start = 0
while start < length:
# A word can only begin on a lowercase letter, never on a separator
# or a (necessarily non-joiner) hyphen.
if not text[start].islower():
start += 1
continue
end = start
while end < length and (text[end].islower() or is_joiner(end)):
end += 1
word_count[text[start:end]] += 1
start = end
return [word_count[query] for query in queries]
Why this is safer:
is_letterperforms the bounds check itself (0 <= idx < length), so neitheridx - 1noridx + 1can ever raise anIndexError.is_joinerencodes the full definition symmetrically (previous and next), so you cannot accidentally enforce only one side.- The word-start guard
text[start].islower()cleanly rejects leading hyphens, spaces, digits, and any other character in a single condition, rather than relying on a hardcoded" -"set that you must remember to keep in sync.
This makes the three boundary cases — leading hyphen, trailing hyphen, and end-of-string — impossible to get wrong by construction, rather than relying on careful short-circuit ordering.
Ready to land your dream job?
Unlock your dream job with a 5-minute quiz for a personalized study roadmap!
Get My RoadmapWhich of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity describes how the time needed
Want a Structured Path to Master System Design Too? Don’t Miss This!