Search This Blog
Welcome to 1printf(), your ultimate destination for C, C++, Linux, Data Structures, and Microcontroller programming! 🚀 🔹Learn advanced coding techniques in C& C++ 🔹Master Linux internals & shell scripting 🔹Deep dive into Data Structures & Algorithms 🔹Explore Embedded Systems & Microcontrollers (8051,UART, RTOS) 🔹Get hands-on coding tutorials, project ideas,and interview preparation tips Whether you're a beginner or an experienced programmer, this channel will help you
Featured
- Get link
- X
- Other Apps
Solve LeetCode 30 Substring with Concatenation of All Words in C++ using sliding window and frequency maps
Substring with Concatenation of All Words in C++
LeetCode 30 · sliding window · frequency maps · string_view
Table of Contents
- Problem Statement
- Approach
- Algorithm
- C++ Program
- Input
- Sample Output
- Output
- Explanation
- Dry Run
- Flow of Execution
- Time Complexity
- Space Complexity
- Applications
- Key Points
- Interview Questions
- Frequently Asked Questions
- Conclusion
Problem Statement
30. Substring with Concatenation of All Words
Given a string s and an array of strings words, where every word has the same length, find all starting indices of substrings that are a concatenation of every word exactly once, in any order.
Approach
This solution uses a sliding window and two frequency maps. Since every word has the same length, the string is checked in chunks of len characters.
freq stores the required frequency of each word. temp stores the frequencies in the current window. count tracks the number of word-sized chunks in the window. If a word occurs too many times, the left side moves forward. If a chunk is not a required word, the current window is reset.
The outer loop checks each alignment from 0 to len - 1, ensuring that matches beginning at different offsets are not missed.
Algorithm
- Calculate
n,m, andlen. - Create a
string_viewreferring tos. - Build
freqfrom the words array. - Try each alignment from 0 to
len - 1. - Move
rightby one word length at a time. - If the chunk is required, update
tempandcount. - Remove chunks from the left while a word occurs too many times.
- If
count == m, saveleftand move the window forward by one word. - If the chunk is unknown, clear the current window.
- Return
res.
C++ Program
Input
s = "barfoothefoobarman" words = ["foo", "bar"]
Each word has length 3, so a valid concatenation has 6 characters.
Sample Output
[0, 9]
Output
The function returns the starting indices of matching concatenations.
s = "barfoothefoobarman", words = ["foo", "bar"] → [0, 9] s = "wordgoodgoodgoodbestword", words = ["word", "good", "best", "word"] → [] s = "barfoofoobarthefoobarman", words = ["bar", "foo", "the"] → [6, 9, 12]
Explanation
Step 1: Lengths and word size
const int n = s.length(), m = words.size(), len = words[0].length();
n is the string length, m is the number of words, and len is the length of each word.
Step 2: Frequency maps
unordered_map<string_view,int> freq, temp;
freq stores how often each word is required; temp stores how often each word appears in the current window. string_view refers to existing character data instead of owning a copy.
Step 3: Build the required counts
for(int i = 0; i < m; ++i) ++freq[words[i]];
Each occurrence in words increments its required frequency, including duplicate words.
Step 4: Check every alignment
for(int i = 0; i < len; ++i)
The outer loop checks all possible offsets within a word length. The inner loop moves through aligned chunks of size len.
Step 5: Process each chunk
string_view str = ss.substr(right , len);
if(freq.find(str) != freq.end()){
++temp[str];
++count;
}If the chunk is one of the required words, its current frequency and the number of chunks in the window increase.
Step 6: Remove excess words
while(temp[str] > freq[str]){
string_view str1 = ss.substr(left , len);
--temp[str1];
--count;
left += len;
}If a word appears too many times, remove chunks from the left until its frequency is valid.
Step 7: Save a complete match
if(count == m){
res.push_back(left);
--temp[ss.substr(left , len)];
--count;
left += len;
}When the window contains exactly m required chunks, save its starting index and move forward one word so overlapping matches can still be found.
Step 8: Reset after an unknown chunk
temp.clear(); count = 0; left = right + len;
A chunk that is not a required word breaks the current candidate window, so the scan starts again after it.
Step 9: Return indices
return res;
After all alignments have been checked, res contains the matching starting positions.
Dry Run
Input: s = "barfoothefoobarman", words = ["foo", "bar"]
Required word length is 3; the total concatenation length is 6.
| Index | Chunk | Action |
|---|---|---|
| 0 | bar | Required word; count = 1 |
| 3 | foo | Both words found; save index 0 |
| 6 | the | Unknown word; reset window |
| 9 | foo | Required word; count = 1 |
| 12 | bar | Both words found; save index 9 |
Final result: [0, 9].
Why check multiple offsets?
With word length 3, a match can start at an index with remainder 0, 1, or 2 when divided by 3. The outer loop checks all these alignments.
Flow of Execution
Start | v Read s and words | v Build freq map | v Choose alignment i | v Read next len-sized chunk | v Is chunk required? | Yes | No v v Update temp/count Clear temp | Reset count v Move left Too many copies? | | | v | Remove from left | | | v | count == m? | | Yes | v | Save left; remove one chunk | v Advance right by len | v More chunks/alignments? | Yes | No v v Continue Return res
Time Complexity
| Part | Complexity |
|---|---|
| Build frequency map | Average O(m × len) |
| Sliding-window scans | Average O(n × len) |
| Overall | Average O((n + m) × len) |
Across all alignments, the right pointer processes O(n) word-sized chunks in total. Hashing and comparing each chunk can take O(len), so the useful average-case bound is O((n + m) × len), assuming average hash-table behavior. Hash-table worst cases may be slower.
Space Complexity
The frequency maps use O(m) entries in the worst case. The result vector uses O(k) space for k matching indices. Therefore, auxiliary space excluding output is O(m), and including output is O(m + k). string_view refers to existing characters rather than copying each substring.
Applications
- Learning fixed-size sliding windows.
- Finding word concatenations in strings.
- Counting word frequencies in a moving window.
- Practising hash maps and frequency counting.
- Preparing for string and DSA coding interviews.
- Learning how C++
string_viewworks.
Key Points
- Every word has the same length.
freqstores required counts andtempstores current-window counts.counttracks the number of chunks in the window.- The outer loop checks every alignment from 0 to
len - 1. - The right pointer moves by
len. - Unknown chunks reset the current window.
string_viewdoes not own the underlying characters.- The code assumes
wordsis non-empty, as in the LeetCode constraints.
Interview Questions
- What does this problem ask us to find?
- Why must all words have the same length?
- Why is a sliding window suitable?
- Why are two frequency maps used?
- What does
countrepresent? - Why does the outer loop check each alignment?
- Why does
rightadvance bylen? - Why does the window shrink when a word appears too often?
- What happens when a chunk is not in
freq? - Why remove one word after saving a match?
- What is the difference between
stringandstring_view? - What is the time complexity?
- What is the space complexity?
- How are duplicate words handled?
Frequently Asked Questions
1. What does the function return?
It returns all starting indices where every word appears exactly as many times as required.
2. Can words appear in any order?
Yes. The words can appear in any order, but each required frequency must be satisfied.
3. Why process chunks?
All words have equal length, so each candidate substring can be divided into word-sized chunks.
4. Why is there an outer loop?
It checks different starting offsets so valid matches are not missed.
5. What if a word appears too many times?
The left side moves forward until the count of that word is no longer excessive.
6. Why clear the map for an unknown chunk?
An unknown chunk cannot belong to a valid concatenation at that alignment, so the window restarts after it.
7. Does string_view copy data?
No. It views existing character data, which must remain alive and unchanged while the view is used.
8. What is the time complexity?
The average-case bound accounting for hashing chunks is O((n + m) × len), assuming average hash-table behavior.
9. What is the space complexity?
The maps use O(m) entries and the output uses O(k) space, for O(m + k) total storage including results.
Conclusion
LeetCode 30 can be solved using a sliding window, frequency maps, and string_view. The algorithm checks every word alignment, shrinks the window when a word appears too often, and resets after chunks that are not required words.
The average-case time bound accounting for chunk hashing is O((n + m) × len). Frequency maps use O(m) entries, in addition to the returned indices.
Search Description
LeetCode 30 Substring with Concatenation of All Words C++ solution using sliding window, unordered_map, frequency counting and string_view. Includes algorithm, dry run, flow of execution, time and space complexity, interview questions and FAQs.
Keywords
Substring with Concatenation of All Words, LeetCode 30 C++ solution, sliding window C++, string_view C++, unordered_map C++, frequency map, substring problems, DSA in C++, coding interview questions, LeetCode string problems
Hashtags
#CppProgramming #Cpp #LeetCode #SlidingWindow #Substring #StringProblems #DSA #CodingInterview #Algorithms #LearnCpp #1printf
Popular Posts
C++ Program for Hybrid Inheritance (All Types Together)
- Get link
- X
- Other Apps
C++ Program for Function Overloading Example
- Get link
- X
- Other Apps
Comments
Post a Comment