Write a Java program to find the smallest window in a string containing all characters of another string.

Step 1: Break Down the Problem

To find the smallest window in a string that contains all characters of another string, we can break the problem into the following manageable parts:

1. Count the frequency of characters in the target string.
2. Slide a window over the main string and keep track of the characters within the window.
3. Check if the current window contains all the characters of the target string.
4. Update the window to find the smallest valid one.

Step 2: Relevant Concepts

• Use a hash map to store character frequencies.
• Use two pointers (or a sliding window) technique to explore possible windows.

Step 3: Analysis and Detail

We'll implement the solution using the sliding window approach, maintaining counts of characters and adjusting the window size as necessary.

Step 4: Verify and Summarize

The resulting Java program will successfully identify the smallest substring containing all characters from the given target string.

Final Answer

Here’s a sample Java program to find the smallest window:

import java.util.HashMap;

public class SmallestWindow {

    public static String findSmallestWindow(String str, String target) {
        HashMap<Character, Integer> targetCount = new HashMap<>();
        for (char c : target.toCharArray()) {
            targetCount.put(c, targetCount.getOrDefault(c, 0) + 1);
        }

        int start = 0, minLength = Integer.MAX_VALUE, minStart = 0, count = 0;
        HashMap<Character, Integer> windowCount = new HashMap<>();

        for (int end = 0; end < str.length(); end++) {
            char endChar = str.charAt(end);
            if (targetCount.containsKey(endChar)) {
                windowCount.put(endChar, windowCount.getOrDefault(endChar, 0) + 1);
                if (windowCount.get(endChar) <= targetCount.get(endChar)) {
                    count++;
                }
            }

            while (count == target.length()) {
                if (minLength > end - start + 1) {
                    minLength = end - start + 1;
                    minStart = start;
                }

                char startChar = str.charAt(start);
                if (windowCount.containsKey(startChar)) {
                    windowCount.put(startChar, windowCount.get(startChar) - 1);
                    if (windowCount.get(startChar) < targetCount.get(startChar)) {
                        count--;
                    }
                }
                start++;
            }
        }

        return (minLength == Integer.MAX_VALUE) ? "" : str.substring(minStart, minStart + minLength);
    }

    public static void main(String[] args) {
        String str = "ADOBECODEBANC";
        String target = "ABC";
        System.out.println("Smallest window is: " + findSmallestWindow(str, target));
    }
}

This program defines a method to find the smallest window containing all characters from the target string, then tests it with sample inputs.