Smallest Window Problem in Java
Given two strings, pattern and string, the goal is to identify the smallest substring in a string that contains every character in the pattern.
Example 1:
Input:
String str = "Welcome to the Java world"
String pattern = "vwdl"
Output:
The smallest window is va world.
Explanation:
The string "va world" contains all the characters present in the pattern "vwdl". Hence the output is "va world" which is also a smallest window string.
Example 2:
Input:
String str = "Hello Welcome to Javatpoint"
String pattern = "Hol"
Output:
The smallest window is Hello.
Explanation:
The string "Hello" contains all the characters present in the pattern "Hol". Hence the output is "Hello" which is also a smallest window string.
Approach: Using Binary Search
The idea is to determine whether a window of size "mid" is valid (i.e., contains every character in the "pattern" string). If so, then all windows larger than "mid" are going to be considered valid. In the same way, all windows smaller than "mid" will be invalid if a window of size "mid" is invalid. This feature makes it feasible for us to use binary search efficiently.
Algorithm:
Step 1: Initialize low and high (low as 'l' and high as 'h') to 1 and string length, respectively, to represent the smallest and largest answers that are possible.
Step 2: Find any substring of length mid in the string that contains every character in the pattern for any value mid.
Step 3: If such a substring of length does exist, identify its beginning index, update high to mid-1, then look for substrings with lengths less than mid.
Step 4: Else, if any such substring does not exist, update low to mid+1 and look for substrings with lengths greater than mid.
Implementation:
FileName: SmallestWindowBinarySearch.java
import java.util.Arrays;
import java.io.*;
public class SmallestWindowBinarySearch
{
// Function to determine whether any substring of length mid contains all of the pattern's characters
static boolean isValid(String s, String pattern, int m, int[] start)
{
// Determine how frequently each character appears in the pattern.
int[] countfreq = new int[256];
// 'dist' denotes the Number of unique characters stored in the pattern
int dist = 0;
boolean found = false;
// Determine how often each character appears in the pattern.
for (char c : pattern.toCharArray())
{
countfreq[c]++;
if (countfreq[c] == 1)
dist++;
}
// Keeps track of how many characters are in a size mid substring in str
// whose frequency matches that of the pattern.
int currentCount = 0;
for (int i = 0; i < s.length(); i++)
{
countfreq[s.charAt(i)]--;
if (countfreq[s.charAt(i)] == 0)
{
currentCount++;
}
if (i >= m)
{
countfreq[s.charAt(i - m)]++;
if (countfreq[s.charAt(i - m)] == 1)
{
currentCount--;
}
}
if (i >= m - 1)
{
// Substring of length mid found that
// includes all of the pattern's characters
if (currentCount == dist)
{
found = true;
// Stores that substring's initial index in memory
start[0] = (i - m) + 1;
break;
}
}
}
return found;
}
// Function to determine which substring of
//The pattern has all of the characters in it.
static String SmallestSubstring(String s, String pattern)
{
int Stringlength = s.length();
int Patternlength = pattern.length();
String smallestSubstring = "";
int minLength = Integer.MAX_VALUE;
// Lower boundary and Uper Boundary for Binary Search
int low = 1, high = Stringlength;
// starting index of the minimum length substring is stored.
int[] index = new int[1];
// Apply the binary Search
while (low <= high)
{
int m = (low + high) / 2;
int[] start = new int[1];
// If all the characters in the pattern are present
// in a substring of length mid, then update min.
// In case of an update min, update the length and upperBound.
if (isValid(s, pattern, m, start))
{
if (m < minLength)
{
minLength = m;
index[0] = start[0];
}
high = m - 1;
}
else
{
low = m + 1;
}
}
return smallestSubstring = s.substring(index[0], index[0] + minLength);
}
public static void main(String[] args)
{
String s = "Welcome to the Java world";
String pattern = "vwdl";
System.out.println("The Input String :" + s);
System.out.println("The Pattern :" + pattern);
System.out.println("The smallest window is: " + SmallestSubstring(s, pattern));
}
}
Output:
The Input String :Welcome to the Java world
The Pattern :vwdl
The smallest window is: va world
Complexity Analysis:
The Time Complexity is O(N *logN), where N represents the length of a given string, and the Space Complexity is O(1), which is constant.
Approach: Brute Force Algorithm
The approach is based on a brute force algorithm. We verify if each substring in the string str is an acceptable window or not. We update our result if we determine that it is a valid smallest window.
Algorithm:
Step 1: Initialize an empty string called resultString.
Step 2: Return an empty string if the pattern's length exceeds the length of str.
Step 3: Update the frequency of each character in the pattern by iterating through it and updating countfreq1[].
Step 4: Initialize len to n + 1, where n is the str's length.
Step 5: Go through each of the str's substrings one by one.
Step 5.1: Create a countfreq2[] frequency array for the substring.
Step 5.2: Verify that the substring contains every character in the pattern.
Step 5.3: Update resultString if its length is less than len.
Step 6: Return resultString accordingly. Return an empty string if it's empty; if not, return resultString.
Implementation:
FileName: BruteForceSmallestWindow.java
import java.io.*;
import java.util.*;
public class BruteForceSmallestWindow
{
static String SmallestWindow(String str, String pattern)
{
String resultString = "";
if(pattern.length() > str.length())
{
return "";
}
int countfreq1[] = new int[128];
// creating a frequency array for storing the character frequencies in a string pattern
int n = str.length();
for(int i = 0; i < pattern.length(); i++)
{
countfreq1[(int)pattern.charAt(i)]++;
}
int len = n + 1;
// iterating through each substring in the string str
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
{
int countfreq2[] = new int[128];
//Constructing a frequency array for storing the substring's character frequencies
for(int k = i; k <= j; k++)
{
countfreq2[str.charAt(k)]++;
}
// determining whether a substring includes every letter in the string pattern
for(int k = 0; k < 128; k++)
{
if(countfreq2[k] < countfreq1[k])
{
break;
}
if(k == 127)
{
// If the substring has every character in it,
//We'll see if it can be reduced to the
// smallest character and adjust the result.
if(len > (j - i))
{
len = j - i;
resultString = str.substring(i, j + 1);
}
}
}
}
}
// return the empty string " in the case that resultString is empty;
//If not, resultString is returned.
return (resultString.length() == 0 ? "" : resultString);
}
public static void main(String[] args) {
String s = "Welcome to the Java world";
String pattern = "vwdl";
System.out.println("The Input String: " + s);
System.out.println("The Pattern: " + pattern);
String answer = SmallestWindow(s, pattern);
System.out.println("The Minimum window : " + answer);
}
}
Output:
The Input String: Welcome to the Java world
The Pattern: vwdl
The Minimum window : va world
Complexity Analysis:
The time complexity is O(n3) since we are searching over all substrings, and there are O(n2) substrings. It takes O(n) time to determine whether a given substring can be a valid window. The space complexity is O(1), which is constant.
Approach: Using Pointers
Two strings are provided, i.e., str and pattern, to us. Our task is to identify a substring such that the pattern occurs inside the string's subsequence. In case there are several valid substrings, the substrings with the smallest size need to be given as an output. Any valid substring of the string str can be taken into consideration if multiple instances of it are identical in length.
Algorithm:
Step 1: Initialise an empty string result to store the shortest window,
Step 2: Initialise two pointers, p1 and p2, beginning at the pattern's and the string's beginnings, respectively.
Step 3: Call p1 to iterate over the characters in str.
Step 4: Determine whether the character at p1 in str and the character at p2 in the pattern match.
Step 4.1: Increment by p2.
Step 4.2: The pattern has been found in the whole if p2 reaches the end of it.
Step 4.2.1: To reduce the window from the left until every character in the pattern appears, identify the end point as e and decrement p1.
Step 4.2.2: If the window size is smaller than it was in the past, then update the minimum.
Step 5: Return the str substring that corresponds to the smallest window that was identified.
Implementation:
FileName: PointersSmallestWindow.java
import java.io.*;
import java.util.*;
public class PointersSmallestWindow
{
public static String SmallestWindow(String str, String pattern)
{
// Initially, the resultant window should be blank.
String result = "";
int p2 = 0;
int min = str.length() + 1;
for (int p1 = 0; p1 < str.length(); p1++)
{
// In case the characters in both strings are identical, then increase the pointer of P2.
// Since p1 is the loop variable, it will automatically get increased.
if (str.charAt(p1) == pattern.charAt(p2))
{
p2 = p2 + 1;
//The entire string pattern has been evaluated. Thus, this represents the right time for minimizing the window.
if (p2 == pattern.length())
{
int e = p1 + 1;
p2 = p2 - 1;
// decrement the window size
while (p2 >= 0)
{
if (str.charAt(p1) == pattern.charAt(p2))
{
p2 = p2 - 1;
}
p1 = p1 - 1;
}
p2 = p2 + 1;
p1 = p1 + 1;
// since we found a window that is less in length, we must update the window.
if (e - p1 < min)
{
// Update the variable minimum
min = e - p1;
// Update the window
result = str.substring(p1, e);
}
}
}
}
// returning the final answer, which remains stored in the window
return result;
}
public static void main(String argvs[])
{
// creation of an object for the class
PointersSmallestWindow obj = new PointersSmallestWindow();
String str = "Welcome to the Java world";
String pattern = "Wm";
System.out.println("The Input String: " + str);
System.out.println("The Pattern: " + pattern);
String answer = obj.SmallestWindow(str, pattern);
System.out.println("The Minimum window is : " + answer);
}
}
Output:
The Input String: Welcome to the Java world
The Pattern: Wm
The Minimum window is : Welcom
Complexity Analysis:
The time complexity for the above approach is O(n2), where n represents the total number of characters present in the given string. The space complexity is O(1), which is constant.
Approach: Using Hashing and a two-pointer technique
The idea is to identify the smallest possible window by removing characters from the window's beginning after applying the two-pointer technique to the hash array of the pattern string.
Algorithm:
Step 1: Check whether the string's length is less than the pattern's specified length. Then, no window exists.
Step 2: Store each character that appears in the provided pattern into a hash array (such as hash_pattern[]).
Step 3: Apply the two-pointer method effectively.
Step 4: Start by comparing each character in the pattern with each character in the string; if a match is found, increase the count.
Step 5: Check that (count == pattern length). A window is found if it's true.
Step 6: If a window appears, consider minimizing it by reducing unnecessary characters from the window's beginning.
Step 6.1: Delete the first character.
Step 6.2: Check to the right for this deleted character.
Step 6.3: If the object exists, continue the step by verifying that the count and pattern length match.
Step 7: Return the minimal length window and update the minimum length.
Implementation:
FileName: SmallestWindowTwoPointer.java
import java.io.*;
import java.util.*;
public class SmallestWindowTwoPointer
{
static final int charcount = 256;
static String SmallestWindow(String s, String pattern)
{
int n = s.length();
int m = pattern.length();
// Check whether the string's length is less than the pattern's length.
// If so, there cannot be such a window.
if (n < m)
{
return "";
}
int hash_pattern[] = new int[charcount];
int hash_string[] = new int[charcount];
// Store occurrences of the characters in the pattern
for (int i = 0; i < m; i++)
hash_pattern[pattern.charAt(i)]++;
int start = 0, first_index = -1;
int Minlen = Integer.MAX_VALUE;
// traverse the string and count characters
int count = 0;
for (int j = 0; j < n; j++)
{
// Count the number of occurrences
// a character appears in the string
hash_string[s.charAt(j)]++;
if (hash_string[s.charAt(j)] <= hash_pattern[s.charAt(j)])
count++;
// characters are matched
if (count == m)
{
// Minimize the window
while (hash_string[s.charAt(start)] > hash_pattern[s.charAt(start)] || hash_pattern[s.charAt(start)]== 0)
{
if (hash_string[s.charAt(start)] > hash_pattern[s.charAt(start)])
hash_string[s.charAt(start)]--;
start++;
}
//Update the window size
int window_len = j - start + 1;
if (Minlen > window_len)
{
Minlen = window_len;
first_index = start;
}
}
}
// If no window exists
if (first_index == -1)
{
return "";
}
// Return the first index and length of the substring, starting at Minlen,
return s.substring(first_index, first_index + Minlen);
}
public static void main(String[] args)
{
String s = "Welcome to the Java world";
String pattern = "vwdl";
System.out.println("The Input String :" + s);
System.out.println("The Pattern :" + pattern);
System.out.println("The smallest window is: " + SmallestWindow(s, pattern));
}
}
Output:
The Input String :Welcome to the Java world
The Pattern :vwdl
The smallest window is: va world
Complexity Analysis:
The Time Complexity of the above approach is O(N), where N represents the length of the string and the Space Complexity is O(1)