Minimum Window Subsequence

XXX. Minimum Window Subsequence

Two-Pointer

Hash Map

Problem Statement:

Given two strings s1 and s2, find the minimum window in s1 which contains all the characters of s2 in the same order.

Algorithm:

The algorithm uses a two-pointer and hash map approach to track the positions of characters in s1 that match the sequence of s2:

1. Preprocess s1 to build a map of character indices for faster access.
2. Iterate through each possible starting position in s1:
• For each character in s2, find its next valid position in s1 using the precomputed map.
• Maintain a pointer to track the last matched position in s1.
3. Calculate the window size if all characters in s2 are matched. Update the result if this window is smaller than the current minimum.

Complexity:

Time Complexity: O(n * m), where n is the length of s1 and m is the length of s2. For each starting position in s1, the characters of s2 are matched.
Space Complexity: O(n), for storing the hash map of indices.

Java Implementation:

class Solution {
    public String minWindow(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        String answer = "";

        // Step 1: Preprocess s1 to build a map of character indices.
        // This allows quick lookup of where each character in s1 appears.
        HashMap> indices = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c = s1.charAt(i);
            indices.putIfAbsent(c, new ArrayList<>());
            indices.get(c).add(i);
        }

        // Array to track the next valid index for each character in s2.
        int[] ind = new int[m];

        // Step 2: Iterate through each possible starting position in s1.
        for (int start = 0; start < n; start++) {
            int prev = start - 1; // Tracks the last matched index in s1.

            // Step 3: Match each character in s2.
            for (int j = 0; j < m; j++) {
                // If a character in s2 is not in s1, the sequence cannot be formed.
                if (!indices.containsKey(s2.charAt(j))) return "";

                ArrayList curIndices = indices.get(s2.charAt(j));

                // Find the next valid index for s2[j] in s1 after 'prev'.
                while (ind[j] < curIndices.size() && curIndices.get(ind[j]) <= prev) ind[j]++;

                // If no valid index is found, return the current answer.
                if (ind[j] == curIndices.size()) return answer;

                // Update 'prev' to the current index of the matched character.
                prev = curIndices.get(ind[j]);
            }

            // Step 4: Calculate the window size and update the answer if it's smaller.
            if (answer.isEmpty() || prev - start + 1 < answer.length()) 
                answer = s1.substring(start, prev + 1);
        }

        return answer;
    }
}