Let's say that we are checking for the subsequence "abcd" in the string "abcabcd".
First we incrementally look for indices of a,b,c,d. We get to the end of the string. In order to make sure that this is the minimum window between the start and the end, we must also decrementally look for characters of the target string that have appeared before the end index. If we only had the string "abcwwwd" to search in, the only previous occurrence of the target would have indeed been the entire string. However, we need to go back to find the character c starting before, b starting before, a starting before etc.
Approach 2-Dynamic Programming
Over the range of the String S, we can look for closest subsequence starts. Then, for all occurrences of the second character of the string T in S, we look for the closest first indices. For the third character, closest second character index before, which themselves point out to the subsequence start. With this incremental structure, we find the closest subsequence starts for the last character of the target string. We look for the minimum and return the corresponding substring. It's to be noted that this approach is slower, although worth learning about.
Resolves: #232
Approach 1-Character Finding
Let's say that we are checking for the subsequence "abcd" in the string "abcabcd". First we incrementally look for indices of a,b,c,d. We get to the end of the string. In order to make sure that this is the minimum window between the start and the end, we must also decrementally look for characters of the target string that have appeared before the end index. If we only had the string "abcwwwd" to search in, the only previous occurrence of the target would have indeed been the entire string. However, we need to go back to find the character c starting before, b starting before, a starting before etc.
Approach 2-Dynamic Programming
Over the range of the String S, we can look for closest subsequence starts. Then, for all occurrences of the second character of the string T in S, we look for the closest first indices. For the third character, closest second character index before, which themselves point out to the subsequence start. With this incremental structure, we find the closest subsequence starts for the last character of the target string. We look for the minimum and return the corresponding substring. It's to be noted that this approach is slower, although worth learning about.