window

Problem Statement Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Example: The array is [1 3 -1 -3 5 3 6 7], and w is 3. Window position Max \--------------- ----- $1 3 -1$ -3 5 3 6 7 3 1 $3 -1 -3$ 5 3 6 7 3 1 3 $-1 -3 5$ 3 6 7 5 1 3 -1 $-3 5 3$ 6 7 5 1 3 -1 -3 $5 3 6$ 7 6 1 3 -1 -3 5 $3 6 7$ 7 Input: A long array A[], and a window width w [Read More]

Some points to note about this String matching algorithm: uses an hashing function; preprocessing phase in O(m) time complexity and constant space; searching phase in O(m__n) time complexity; O(n_+_m) expected running time. Instead of checking at each position of the text if the pattern occurs or not, it is better to check first if the contents of the current string “window” looks like the pattern or not. In order to check the resemblance between these two patterns, a hashing function is used. [Read More]

Problem Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example S = “ADOBECODEBANC”, T = “ABC”, Minimum window is “BANC”. Note: If there is no such window in S that covers all characters in T, return the emtpy string “”. If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S. [Read More]