Count Valid Word Occurrences - Video Solutions
weekly contest 501| leetcode 3925 | leetcode 3926| leetcode 3927| leetcode 3928| Dijkstra| DSA
Count Valid Word Occurrences - Video Solution
Watch 5 video solutions for Count Valid Word Occurrences, a medium level problem involving Array, Hash Table, String. This walkthrough by Code With Vick has 558 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
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 <= 105āāāāāāāchunks[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 <= 105āāāāāāāqueries[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.
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 |