Skip to main content

Featured

LeetCode 76: Minimum Window Substring – Optimal C++ Solution Using Sliding Window

Minimum Window Substring in C++ LeetCode 76 · Sliding Window · Frequency Counting · Two Pointers 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 76. Minimum Window Substring Given two strings s and t , return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such substring exists, return an empty string. Approach This solution uses the Sliding Window technique with two pointers, start and end , and a frequency array. The map array stores the required frequency of each character in string t . The variable count tracks how many characters are still required to form a valid window. The end pointer expands the window by including characters from string s . ...

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

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

  1. Calculate n, m, and len.
  2. Create a string_view referring to s.
  3. Build freq from the words array.
  4. Try each alignment from 0 to len - 1.
  5. Move right by one word length at a time.
  6. If the chunk is required, update temp and count.
  7. Remove chunks from the left while a word occurs too many times.
  8. If count == m, save left and move the window forward by one word.
  9. If the chunk is unknown, clear the current window.
  10. Return res.

C++ Program

substring_concatenation.cpp

  

Input

input
s = "barfoothefoobarman"
words = ["foo", "bar"]

Each word has length 3, so a valid concatenation has 6 characters.

Sample Output

terminal
[0, 9]

Output

The function returns the starting indices of matching concatenations.

terminal
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.

IndexChunkAction
0barRequired word; count = 1
3fooBoth words found; save index 0
6theUnknown word; reset window
9fooRequired word; count = 1
12barBoth 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

flow
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

PartComplexity
Build frequency mapAverage O(m × len)
Sliding-window scansAverage O(n × len)
OverallAverage 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_view works.

Key Points

  • Every word has the same length.
  • freq stores required counts and temp stores current-window counts.
  • count tracks 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_view does not own the underlying characters.
  • The code assumes words is non-empty, as in the LeetCode constraints.

Interview Questions

  1. What does this problem ask us to find?
  2. Why must all words have the same length?
  3. Why is a sliding window suitable?
  4. Why are two frequency maps used?
  5. What does count represent?
  6. Why does the outer loop check each alignment?
  7. Why does right advance by len?
  8. Why does the window shrink when a word appears too often?
  9. What happens when a chunk is not in freq?
  10. Why remove one word after saving a match?
  11. What is the difference between string and string_view?
  12. What is the time complexity?
  13. What is the space complexity?
  14. 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

Comments

Popular Posts

🌙