Can someone explain why this algorithm requires going backwards through the subsequence again once a match has been found?
Course: Grokking Coding Interview Patterns in C++ - Learn Interactively
Lesson: Minimum Window Subsequence - Grokking Coding Interview Patterns in C++
There seems to be no benefit to reading backwards once a subsequence has been found. The same result can be had just by tracking where the initial match of the subsequence was made. This seems much simpler to me.
string MinWindow(const string& str1, const string& str2) {
int minLength = INT_MAX;
string minSubstring = "";
int start = 0;
int i1 = 0;
int i2 = 0;
while (i1 < str1.size()) {
if (str1[i1] == str2[i2]) {
// If this is the start of the substring, mark it
if (i2 == 0) {
start = i1;
}
i2++; // Only advance i2 if there was a match
// If this is the end of the substring, use start to calculate length
if (i2 == str2.size()) {
int curLength = (i1 + 1) - start;
if (curLength < minLength) {
minLength = curLength;
minSubstring = str1.substr(start, curLength);
}
// Reset pointers for next iteration
i1 = start; // It wil start next iteration at start + 1
i2 = 0;
}
}
i1++; // Always advance i1
}
return minSubstring;
}
Course: https://www.educative.io/courses/grokking-coding-interview-patterns-cpp
Lesson: Minimum Window Subsequence - Grokking Coding Interview Patterns in C++
Hi @Peter_Hastie,
Thank you for sharing your solution with us. We have verified that your solution, indeed, is correct and solves the Minimum Window Subsequence problem without traversing the window backwards. This shows your excellent problem solving skills.
Now, let me explain the reason of iterating backwards once the window has been found. Let’s take an example to understand the algorithm clearly.
str1 = “azssssaztf”
str2 = “saz”
For the input strings given above, the algorithm will iterate over str1 until all the characters of str2 have been found in the same order as they are present in str2. So, the first window that we will get from str1 will be “ssssaz”. Now, let’s try your approach on this window. As you can see that from the window extracted from str1, if we do not iterate backwards, we will be continuing iteration from character “s” present at index 3 in str1 after the first match. Then, the second match that we will get is “sssaz”. After this, the algorithm will start iteration from character “s” present at index 4 in str1. Then, the third match that we will get is “ssaz”. After this match, the algortihm will start iteration over str1 from character “s” present at index 5 in str1. Finally, the fourth match will be the minimum subsequence, that is “saz”, which we will get after multiple iterations over the same window.
However, if we iterate backwards over the window, we simultaneously iterate backwards over str2 as its characters are found in the window in backwards order. By doing this, the minimum subsequence containing str2 in the current window can be identified in a single traversal. Then, we continue the iteration over str1 from the start of the minimum subsequence identified. In case of the example given above, when we iterate backwards over the window “ssssaz”, we find out the minimum subsequence to be “saz” after backwards traversal and then we continue the traversal over str1 from character “a” present at index 6 in str1. This makes the algorithm efficient and fast and avoids unnecessary traversal over str1.
I hope this answers your question as to why we go backwards over the window. However, if there are any further confusions, please do ask in the thread so we can address them. We hope you have an amazing experience learning the Educative way!