Smallest Window In A String Containing All The Characters Of Another String

Given two strings s and p. Find the smallest window in the string s consisting of all the characters(including duplicates) of the string p. Return “-1” in case there is no such window present. In case there are multiple such windows of same length, return the one with the least starting index.
Note : All characters are in Lowercase alphabets. 

Examples:

Input: s = "timetopractice", p = "toc"
Output: toprac
Explanation: "toprac" is the smallest
substring in which "toc" can be found.
Input: s = "zoomlazapzo", p = "oza"
Output: apzo
Explanation: "apzo" is the smallest 
substring in which "oza" can be found.

Expected Time Complexity: O(|s|)
Expected Auxiliary Space: O(n), n = len(p)

Constraints: 
1 ≤ |s|, |p| ≤ 105


Approach 01:

#include <vector>
#include <string>
#include <climits>

class Solution {
public:
    std::string smallestWindow(std::string source, std::string pattern) {
        std::vector<int> patternFrequency(26);
        int sourceLength = source.length();
        
        // Count frequency of characters in the pattern
        for (auto &charInPattern : pattern)
            patternFrequency[charInPattern - 'a']++;
        
        std::vector<int> windowCharCount(26, 0);
        int leftPointer = 0, rightPointer = 0;
        int minWindowLength = INT_MAX;
        int startPosition = -1;
        
        // Lambda function to check if the window contains all characters in pattern
        auto containsAllChars = [&]() -> bool {
            for (int i = 0; i < 26; ++i) {
                if (patternFrequency[i] > windowCharCount[i]) 
                    return false;
            }
            return true;
        };
        
        // Sliding window technique
        while (rightPointer < sourceLength) {
            windowCharCount[source[rightPointer] - 'a']++;
            if (!containsAllChars()) {
                rightPointer++;
            } else {
                while (containsAllChars()) {
                    if (rightPointer - leftPointer + 1 < minWindowLength) {
                        minWindowLength = rightPointer - leftPointer + 1;
                        startPosition = leftPointer;
                    }
                    windowCharCount[source[leftPointer] - 'a']--;
                    leftPointer++;
                }
                rightPointer++;
            }
        }
        return minWindowLength == INT_MAX ? "-1" : source.substr(startPosition, minWindowLength);
    }
};

Time Complexity

  • Initial Pattern Frequency Count:

    We iterate through the pattern to count the frequency of its characters. This takes \(O(m)\) time, where \(m\) is the length of the pattern.

  • Sliding Window Iteration (Outer Loop):

    We use a sliding window with two pointers, leftPointer and rightPointer, to traverse the source. The rightPointer iterates through the entire string, leading to an outer loop that runs \(O(n)\), where \(n\) is the length of the source string.

  • Contains All Characters Check (Inner Loop):

    For each window, we check whether the current window contains all characters from the pattern. This check involves iterating through the 26 letters of the alphabet, leading to \(O(26)\), which simplifies to \(O(1)\).

  • Left Pointer Movement (Inner Loop):

    While the window contains all characters, we adjust the window by moving the leftPointer to reduce the size of the window. In the worst case, this can cause the left pointer to move across the entire string. However, each character is processed at most twice (once by the right pointer and once by the left pointer), leading to an overall \(O(n)\) complexity for the left pointer.

  • Overall Time Complexity:

    The outer loop runs \(O(n)\), and since the inner operations involve constant time checks, the overall time complexity is \(O(n + m)\), where \(n\) is the length of the source string and \(m\) is the length of the pattern.

Space Complexity

  • Pattern Frequency Array:

    The patternFrequency array has a fixed size of 26 to store character frequencies, resulting in \(O(1)\) space.

  • Window Character Count Array:

    The windowCharCount array also has a fixed size of 26 for counting characters in the current window, which takes \(O(1)\) space.

  • Other Variables:

    Additional variables such as pointers, integers, and the lambda function do not depend on the size of the input, thus contributing \(O(1)\) space.

  • Overall Space Complexity:

    The overall space complexity is \(O(1)\), as all auxiliary arrays are of constant size.

class Solution:
    def smallestWindow(self, source: str, pattern: str) -> str:
        # Early exit if source or pattern is empty
        if not source or not pattern:
            return "-1"
        
        sourceLength = len(source)
        patternFrequency = [0] * 128  # ASCII size is sufficient for all characters
        windowCharCount = [0] * 128
        
        # Count frequency of each character in the pattern
        for charInPattern in pattern:
            patternFrequency[ord(charInPattern)] += 1
        
        leftPointer = 0
        minWindowLength = float('inf')
        startPosition = -1
        matchedCharCount = 0  # Tracks how many characters from pattern have been matched

        for rightPointer in range(sourceLength):
            currentChar = source[rightPointer]
            windowCharCount[ord(currentChar)] += 1
            
            # If current character's frequency in the window does not exceed its frequency in pattern
            if windowCharCount[ord(currentChar)] <= patternFrequency[ord(currentChar)]:
                matchedCharCount += 1
            
            # When all characters are matched
            while matchedCharCount == len(pattern):
                windowSize = rightPointer - leftPointer + 1
                if windowSize < minWindowLength:
                    minWindowLength = windowSize
                    startPosition = leftPointer
                
                # Try to shrink the window by moving the leftPointer
                charAtLeft = source[leftPointer]
                windowCharCount[ord(charAtLeft)] -= 1
                if windowCharCount[ord(charAtLeft)] < patternFrequency[ord(charAtLeft)]:
                    matchedCharCount -= 1
                leftPointer += 1
        
        return "-1" if startPosition == -1 else source[startPosition:startPosition + minWindowLength]

Time Complexity

  • Initial Pattern Frequency Count:

    We iterate over the pattern to count the frequency of its characters. This takes \(O(m)\) time, where \(m\) is the length of the pattern.

  • Sliding Window (Outer Loop):

    The rightPointer iterates through the entire string source, so the outer loop runs \(O(n)\), where \(n\) is the length of the source.

  • Adjusting Left Pointer (Inner Loop):

    The leftPointer adjusts to minimize the window whenever all characters from the pattern are matched. Since each character in the source string is processed at most twice (once by the right pointer and once by the left pointer), the overall complexity of adjusting the left pointer is \(O(n)\).

  • Overall Time Complexity:

    The outer loop takes \(O(n)\), and the operations within the loop (updating the frequency and shrinking the window) are constant time \(O(1)\), so the overall time complexity is \(O(n + m)\), where \(n\) is the length of the source string and \(m\) is the length of the pattern.

Space Complexity

  • Pattern and Window Frequency Arrays:

    We use two arrays patternFrequency and windowCharCount, each of size 128 (for ASCII characters). These arrays require \(O(1)\) space since their size is fixed.

  • Other Variables:

    Additional variables like leftPointer, minWindowLength, startPosition, and matchedCharCount take up constant space, which is \(O(1)\).

  • Overall Space Complexity:

    The overall space complexity is \(O(1)\), as we only use fixed-size arrays and a few scalar variables.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top