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

#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.