Smallest Window Containing 0, 1, and 2 in Java
Given a string S. The task is to find the length of the smallest substring in a string that contains all three elements 0, 1, and 2. If no substring exits, then return -1.
Example 1
Input: S = “012”
Output: 3
Explanation: The substring 012 is the smallest substring that contains all three elements 0, 1 and 2.
Example 2
Input: S = “0112”
Output: 4
Explanation: The substring 0112 is the smallest substring that contains all three elements 0, 1 and 2.
Example 3
Input: S = “12121”
Output: -1
Explanation: As the character 0 is not present in the string S, therefore no substring containing all the three characters 0, 1 and 2 exists. so, return -1.
Approach 1: Using Sliding Window Approach
A sliding window algorithm to find the smallest window in a string that contains all three characters '0', '1', and '2'. It uses a HashMap to keep track of the frequency of characters in the current window and adjusts the window size accordingly.
Algorithm
Step 1: Initialize a HashMap freq to track the frequency of characters in the current window, set the left pointer left to 0, and set minWindowSize to Integer.MAX_VALUE.
Step 2: Start iterating through the string using the right pointer right.
Step 3: Increment the frequency of the character at right in the freq HashMap.
Step 4: Check if the current window contains all three characters '0', '1', and '2' using the freq HashMap. If so, enter the while loop.
Step 5: While the window contains all three characters, update the minWindowSize if the current window size is smaller. Shrink the window by moving the left pointer left and updating the freq HashMap accordingly.
Step 6: After exiting the while loop, update the minimum window size if a smaller window containing all characters is found.
Step 7: Return the minimum window size or -1 if no window containing all characters is found.
Filename: SmallestWindowUsingSlidingWindow.java
import java.util.HashMap; public class SmallestWindowUsingSlidingWindow { public static int smallestWindowSlidingWindow(String str) { int n = str.length(); HashMapfreq = new HashMap<>(); int left = 0; int minWindowSize = Integer.MAX_VALUE; for (int right = 0; right < n; right++) { char currentChar = str.charAt(right); freq.put(currentChar, freq.getOrDefault(currentChar, 0) + 1); // Check if the current window contains all required characters while (freq.containsKey('0') && freq.containsKey('1') && freq.containsKey('2')) { int windowSize = right - left + 1; if (windowSize < minWindowSize) { minWindowSize = windowSize; // Update the minimum window size } char leftChar = str.charAt(left); freq.put(leftChar, freq.get(leftChar) - 1); // Shrink the window if (freq.get(leftChar) == 0) { freq.remove(leftChar); } left++; // Move the left pointer to shrink the window } } return (minWindowSize != Integer.MAX_VALUE) ? minWindowSize : -1; } public static void main(String[] args) { String str = "0112"; int resultLength = smallestWindowSlidingWindow(str); System.out.println("Length of the smallest window containing 0, 1, and 2: " + resultLength); } }
Output
Length of the smallest window containing 0, 1, and 2: 4
Time Complexity: The time complexity of this algorithm is O(n), where n is the length of the input string. This is because the algorithm iterates through the string only once.
Space Complexity: The space complexity is O(1) for the HashMap freq because it can contain at most 3 characters ('0', '1', '2') at any given time, regardless of the input string size. Thus, the space complexity is constant and does not depend on the input size.
Approach 2: Using Brute Force Approach
The brute force approach to find the smallest window in the input string that contains all three characters '0', '1', and '2'.
Algorithm
Step 1: Iterate through all possible substrings of the input string.
Step 2: Check if each substring contains '0', '1', and '2'.
Step 3: Track the length of the smallest valid window found else return -1.
Filename: SmallestWindowUsingBruteForce.java
public class SmallestWindowUsingBruteForce { public static int smallestWindowBruteForce(String str) { int n = str.length(); int minWindowSize = Integer.MAX_VALUE; // Iterate through all possible substrings for (int i = 0; i < n; i++) { for (int j = i + 2; j < n; j++) { String sub = str.substring(i, j + 1); // Check if the substring contains all three characters '0', '1', and '2' if (containsZeroOneTwo(sub) && sub.length() < minWindowSize) { minWindowSize = sub.length(); } } } return (minWindowSize != Integer.MAX_VALUE) ? minWindowSize : -1; } public static boolean containsZeroOneTwo(String str) { boolean containsZero = false, containsOne = false, containsTwo = false; for (char c : str.toCharArray()) { if (c == '0') containsZero = true; else if (c == '1') containsOne = true; else if (c == '2') containsTwo = true; } return containsZero && containsOne && containsTwo; } public static void main(String[] args) { String str = "0112"; int result = smallestWindowBruteForce(str); System.out.println("Length of the smallest window containing 0, 1, and 2: " + result); } }
Output
Length of the smallest window containing 0, 1, and 2: 4
Time Complexity: The time complexity of an algorithm is O(n^3), where n is the length of the input string. This is because the algorithm iterates through all possible substrings.
Space Complexity: The space complexity of an algorithm is O(1). This is because a constant as the additional space used is not dependent on the input size.
Approach 3: Using Two-Pointers Approach
The two-pointer approach to find the smallest window in the input string that contains all three characters '0', '1', and '2'.
Algorithm
Step 1: Use two pointers, left and right, to define a sliding window.
Step 2: Move the right pointer to expand the window until it contains all required characters.
Step 3: Move the left pointer to shrink the window while maintaining the constraint.
Step 4: Track the length of the smallest valid window found else return -1.
Filename: SmallestWindowUsingTwoPointers.java
public class SmallestWindowUsingTwoPointers { public static int smallestWindowTwoPointer(String str) { int n = str.length(); int left = 0, right = 0; int minWindowSize = Integer.MAX_VALUE; boolean containsZero = false, containsOne = false, containsTwo = false; // Use two pointers to define the window while (right < n) { char currentChar = str.charAt(right); if (currentChar == '0') containsZero = true; else if (currentChar == '1') containsOne = true; else if (currentChar == '2') containsTwo = true; // Shrink the window while all required characters are present while (containsZero && containsOne && containsTwo) { minWindowSize = Math.min(minWindowSize, right - left + 1); char leftChar = str.charAt(left); if (leftChar == '0') containsZero = false; else if (leftChar == '1') containsOne = false; else if (leftChar == '2') containsTwo = false; left++; // Move the left pointer to shrink the window } right++; // Move the right pointer to expand the window } return (minWindowSize != Integer.MAX_VALUE) ? minWindowSize : -1; } public static void main(String[] args) { String str = "0112"; int result = smallestWindowTwoPointer(str); System.out.println("Length of the smallest window containing 0, 1, and 2: " + result); } }
Output
Length of the smallest window containing 0, 1, and 2: 4
Time Complexity: The time complexity of an algorithm is O(n), where n is the length of the input string. This is because both left and right pointers traverse the string only once.
Space Complexity: The space complexity of an algorithm is O(1). This is because a constant as the additional space used is not dependent on the input size.
Approach 4: Using Sorting Approach
The sorting approach to find the length of the smallest window in the input string that contains all three characters '0', '1', and '2'.
Algorithm
Step 1: Convert the input string to a character array and sort it using Arrays.sort.
Step 2: Use two pointers (start and end) to define a sliding window.
Step 3: Move the end pointer to expand the window until it contains all required characters.
Step 4: Move the start pointer to shrink the window while maintaining the constraint.
Step 5: Track the length of the smallest valid window found else return -1.
Filename: SmallestWindowSorting.java
import java.util.Arrays; public class SmallestWindowSorting { public static int smallestWindowSorting(String str) { char[] sortedStr = str.toCharArray(); Arrays.sort(sortedStr); // Sort the characters in the string int minWindowSize = Integer.MAX_VALUE; // Find the smallest window containing '0', '1', and '2' int start = 0, end = 0; while (end < sortedStr.length) { boolean containsZero = false, containsOne = false, containsTwo = false; for (int i = start; i <= end; i++) { if (sortedStr[i] == '0') containsZero = true; else if (sortedStr[i] == '1') containsOne = true; else if (sortedStr[i] == '2') containsTwo = true; } if (containsZero && containsOne && containsTwo) { minWindowSize = Math.min(minWindowSize, end - start + 1); start++; } else { end++; } } return (minWindowSize != Integer.MAX_VALUE) ? minWindowSize : -1; } public static void main(String[] args) { String str = "0112"; int result = smallestWindowSorting(str); System.out.println("Length of the smallest window containing 0, 1, and 2: " + result); } }
Output
Length of the smallest window containing 0, 1, and 2: 4
Time Complexity: The time complexity of an algorithm is O(n log n) due to sorting, where n is the length of the input string.
Space Complexity: The space complexity of an algorithm is O(n) for the sorted character array, where n is the length of the input string.