Smallest window in string consisting of all characters of other string

Given two strings, S and P, the objective is to identify the smallest window within string S that contains all the characters, including duplicates, from string P. If no such window exists, return "-1". If multiple windows of the same size fulfill the criteria, return the one with the smallest starting index. Note that all characters are lowercase alphabets.

Example 1

Input: S = "abcde" P = "xyz" Output: -1 Explanation: Since there are no characters in S that match those in P, there's no window in S containing all characters of P. Hence, the output is -1.

Example 2

Input: S = "abbcadefg" P = "abcdef" Output: "bcadef" Explanation: The smallest window in S containing all characters of P is "bcadef". It starts at index 2 and ends at index 7, encompassing all characters from P.

Approach

To solve this, we use a hashmap to store the frequency of characters in string P, and then iteratively traverse the string S to find the smallest window satisfying the condition. We maintain two pointers to denote the current window, and while traversing S, we update the window boundaries based on the presence of characters from P. The goal is to minimize the size of the window while ensuring that it contains all characters from P. Finally, we return the smallest window found or -1 if no such window exists.

Algorithm

1. Create a hashmap to store the frequency of characters in string P.
2. Initialize two pointers, left and right, to traverse the string S. Also, initialize a variable count to keep track of the number of characters to be found in the window.
3. Iterate through the string S using the right pointer:
   1. If the character at the right pointer is present in string P, decrement its frequency in the hashmap and update the count accordingly.
   2. Check if all characters of string P are found in the current window. If yes, move the left pointer to shrink the window until the condition is satisfied.
4. While shrinking the window, keep track of the smallest window found so far.
5. Once the traversal of string S is complete, return the smallest window found, or -1 if no window containing all characters of string P is found.

Complexity

• Time Complexity: O(|S|), where |S| represents the length of string S. This is because we traverse the string S only once to find the smallest window.
• Space Complexity:  O(n), where n is the length of string P. This is because we use a hashmap to store the frequency of characters in string P, which can have a maximum of n unique characters.

Code

## Java Code

import java.util.*;

public class SmallestWindowFinder {

    public String findSmallestWindow(String s, String p) {
        HashMap<Character, Integer> charFreqP = new HashMap<>();
        for (char c : p.toCharArray()) {
            charFreqP.put(c, charFreqP.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int charsToFind = p.length();
        int minLength = Integer.MAX_VALUE;
        int minLeftIndex = 0;
        boolean windowFound = false;

        while (right < s.length()) {
            char currentChar = s.charAt(right);
            if (charFreqP.containsKey(currentChar)) {
                charFreqP.put(currentChar, charFreqP.get(currentChar) - 1);
                if (charFreqP.get(currentChar) >= 0) {
                    charsToFind--;
                }
                while (charsToFind == 0) {
                    windowFound = true;
                    int currentWindowSize = right - left + 1;
                    if (currentWindowSize < minLength) {
                        minLength = currentWindowSize;
                        minLeftIndex = left;
                    }
                    char leftChar = s.charAt(left);
                    if (charFreqP.containsKey(leftChar)) {
                        charFreqP.put(leftChar, charFreqP.get(leftChar) + 1);
                        if (charFreqP.get(leftChar) > 0) {
                            charsToFind++;
                        }
                    }
                    left++;
                }
            }
            right++;
        }

        if (!windowFound) {
            return "-1";
        }
        return s.substring(minLeftIndex, minLeftIndex + minLength);
    }

    public static void main(String[] args) {
        SmallestWindowFinder finder = new SmallestWindowFinder();
        String s1 = "abcde";
        String p1 = "xyz";
        System.out.println("Input: S = \"" + s1 + "\", P = \"" + p1 + "\"");
        System.out.println("Output: " + finder.findSmallestWindow(s1, p1));

        String s2 = "abbcadefg";
        String p2 = "abcdef";
        System.out.println("\nInput: S = \"" + s2 + "\", P = \"" + p2 + "\"");
        System.out.println("Output: " + finder.findSmallestWindow(s2, p2));
    }
}

Output

Input: S = "abcde", P = "xyz"
Output: -1

Input: S = "abbcadefg", P = "abcdef"
Output: bcadef