Minimum Window Subsequence in Java

In this article, you will be very well acknowledged about the minimum window subsequence, what is the approach and how it is implemented. The example program is also executed and its output is also displayed.

Problem Statement

Find the smallest (contiguous) substring W in string S such that T is a subset of W given strings S and T.

Return the null string "if there isn't a window in S that includes all the characters in T." Return the minimum-length window with the leftmost starting index if there are numerous ones.

Example 1:

Input:

S = asdfghjkl   T = fhl

Output:

The valid output string is W = fghjkl

The string fghjkl includes every letter in the stringfhl.

Example 2 :

Input:

S = zxcvbnm  T = vbm

Output:

The valid output string is W = vbnm

The string vbnm includes every letter in the string vbm

Methodology

First, we'll search for a window that has the entire string T in its actual form. The window will then be reduced as much as it can be while still retaining the requirement that it contain every character in the string T. After that, we can close the window.

The steps for determining the minimal window subsequence are as follows:

Keep the two references ptr1 as well as ptr2 and give them the value 0. Ptr1 and Ptr2 are for the strings S and T, respectively.

When S[ptr1] == T[ptr2], both points should be advanced at once; otherwise, just the ptr1 pointer should be advanced.

The string T is located within string S because when value of ptr2 reaches the size of the string T. We must now make the window smaller. It is crucial to understand why unnecessary characters may enter the window before adjusting the window size.

Let's use the following strings as an example, with S = "ypcdepdde" and T = "pde".

Ptr1 and Ptr2 be placed at the 0 indices of their corresponding strings at the beginning. Since there is an error (y!= p) at index 0, we advance the pointer ptr1 through one position. We now simultaneously move pointers ptr1 and ptr2 by one step. Now, c and d are being compared, which is an incorrect match. Thus, step 1 causes ptr1 to grow. Now when there is a match, both pointers advance at once. The size of a string T is revealed by the ptr2 at the fourth index of a string S, which is three. Thus, the window with size 5 is obtained. Now, when we move going right to left through the window's elements, if we find a match, we cut pt2 by 1. The border should be placed at the point in which the ptr2 becomes 0. Anything beyond the line is undesirable character.

As a result, after shrinking the window, we obtain "pcde" instead of "ypcde" before. Therefore, the character "y" is undesirable.

For the remaining portion of the string S, the same procedure can be repeated.

File name: WindowSeq.java

public class WindowSeq   
{  
  
public static String findMinWindow(String S1, String S2)   
{  
  
// The window is initially bare in the beginning.
String win = "";  
int ptr2 = 0;  
int minimum = S1.length() + 1;  
  
for (int ptr1 = 0; ptr1 < S1.length(); ptr1++)   
{  
  
// Since ptr1 is just the loop variable, it will automatically increase the ptr2 pointer if the //characters in both strings match.
if (S1.charAt(ptr1) == S2.charAt(ptr2))   
{  
ptr2 = ptr2 + 1;  
  
// The entire string S2 has already been examined. As a result, it is now appropriate to //close the window.
if (ptr2 == S2.length())   
{  
int e = ptr1 + 1;  
ptr2 = ptr2 - 1;  
  
// lowering the size of the window 
while (ptr2 >= 0)   
{  
if (S1.charAt(ptr1) == S2.charAt(ptr2))   
{  
ptr2 = ptr2 - 1;  
}  
ptr1 = ptr1 - 1;  
}  
  
ptr2 = ptr2 + 1;  
ptr1 = ptr1 + 1;  
  
// We must alter the window because we discovered one that is shorter.
if (e - ptr1 < minimum)   
{  
  
// the var minimum being updated
minimum = e - ptr1;  
  
// upgrading the window  
win = S1.substring(ptr1, e);  
}  
}  
}  
}  
      
// returning our final response and saving it in the window
return win;  
}  
  public static void main(String argvs[])  
{  
WindowSeq obj = new WindowSeq();  
String s1 = "zxcvbnm";  
String s2 = "vnm";  
System.out.println("For the given strings \"" + s1 + "\" and \"" + s2 + "\"");  
  
String str = obj.findMinWindow(s1, s2);  
System.out.println("The minimum window is : " + str);  
System.out.println();  
    
s1 = "ypcdepdde";  
s2 = "pde";  
System.out.println("For the given strings \"" + s1 + "\" and \"" + s2 + "\"");  
str = obj.findMinWindow(s1, s2);  
System.out.println("The minimum window is : " + str);  
System.out.println();  
    
s1 = "qwertyiop";  
s2 = "tip";  
System.out.println("For the given strings \"" + s1 + "\" and \"" + s2 + "\"");  
str = obj.findMinWindow(s1, s2);  
System.out.println("The minimum window is : " + str);  
  
}  
  
} 

Output

For the given strings “zxcvbnm” and “vnm”
The minimum window is: vbnm
For the given strings “asdfghjkl” and “fhl”
The minimum window is: fghjkl
For the given strings “qwertyuiop” and “tip”
The minimum window is: tyiop

The program's time complexity is O(n2), where n represents the total amount of characters in the string, due to the loops (one for-loop and another while-loop). The program does not consume any additional space, increasing the space's complexity to O (1).