Solution in C++:

#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

double findMaxAverage(vector<int>& nums, int k) {
    int n = nums.size();
    
    // Calculate sum of first window
    int window_sum = 0;
    for (int i = 0; i < k; i++) {
        window_sum += nums[i];
    }
    
    int max_sum = window_sum;
    
    // Slide the window
    for (int i = k; i < n; i++) {
        // Remove leftmost, add rightmost
        window_sum = window_sum - nums[i - k] + nums[i];
        max_sum = max(max_sum, window_sum);
    }
    
    return (double)max_sum / k;
}

Step-by-Step Simulation:

Explanation: This is a classic fixed-size sliding window problem. We calculate the sum of the first k elements, then slide the window by subtracting the leftmost element and adding the new rightmost element. We track the maximum sum and return the average. This avoids recalculating the entire sum for each window, making it O(n) instead of O(nk).

Time Complexity: O(n)

Space Complexity: O(1)

Solution in C++:

#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> char_map;
    int left = 0;
    int max_length = 0;
    
    for (int right = 0; right < s.length(); right++) {
        // If character seen and within current window, move left pointer
        if (char_map.find(s[right]) != char_map.end() && 
            char_map[s[right]] >= left) {
            left = char_map[s[right]] + 1;
        }
        
        // Update character's last position
        char_map[s[right]] = right;
        
        // Update maximum length
        max_length = max(max_length, right - left + 1);
    }
    
    return max_length;
}

Step-by-Step Simulation:

Explanation: We use a variable-size sliding window with a hash map to track the last occurrence of each character. When we encounter a duplicate character within our current window, we move the left pointer to just after the last occurrence. This ensures our window always contains unique characters. The key insight is that we only need to track the last occurrence of each character, not all occurrences.

Time Complexity: O(n)

Space Complexity: O(min(n, m)) where m is the character set size

Solution in C++:

#include <string>
#include <unordered_map>
#include <climits>
using namespace std;

string minWindow(string s, string t) {
    if (s.empty() || t.empty()) {
        return "";
    }
    
    // Count characters needed from t
    unordered_map<char, int> dict_t;
    for (char c : t) {
        dict_t[c]++;
    }
    
    int required = dict_t.size();
    int formed = 0;
    
    // Current window character counts
    unordered_map<char, int> window_counts;
    int left = 0, right = 0;
    int min_len = INT_MAX;
    int min_left = 0;
    
    while (right < s.length()) {
        char c = s[right];
        window_counts[c]++;
        
        // Check if current character's frequency matches requirement
        if (dict_t.find(c) != dict_t.end() && 
            window_counts[c] == dict_t[c]) {
            formed++;
        }
        
        // Try to shrink window from left
        while (left <= right && formed == required) {
            // Update minimum window
            if (right - left + 1 < min_len) {
                min_len = right - left + 1;
                min_left = left;
            }
            
            // Remove leftmost character
            char left_char = s[left];
            window_counts[left_char]--;
            if (dict_t.find(left_char) != dict_t.end() && 
                window_counts[left_char] < dict_t[left_char]) {
                formed--;
            }
            
            left++;
        }
        
        right++;
    }
    
    return (min_len == INT_MAX) ? "" : s.substr(min_left, min_len);
}

Explanation: We use a variable-size sliding window. We expand the window by moving the right pointer and track character frequencies. When all required characters are present (formed == required), we try to shrink the window from the left to find the minimum valid window. We track the minimum length and starting position. The 'formed' variable counts how many unique characters have reached their required frequency, allowing us to know when the window is valid.

Time Complexity: O(|s| + |t|)

Space Complexity: O(|s| + |t|)

Solution in C++:

#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int maxSumSubarray(vector<int>& arr, int k) {
    int n = arr.size();
    if (n < k) {
        return -1;
    }
    
    // Calculate sum of first window
    int window_sum = 0;
    for (int i = 0; i < k; i++) {
        window_sum += arr[i];
    }
    
    int max_sum = window_sum;
    
    // Slide the window
    for (int i = k; i < n; i++) {
        window_sum = window_sum - arr[i - k] + arr[i];
        max_sum = max(max_sum, window_sum);
    }
    
    return max_sum;
}

Explanation: This is a straightforward fixed-size sliding window problem. We maintain a window of size k, calculate its sum, and slide it through the array. At each step, we update the maximum sum found so far. By reusing the previous window's sum and only adjusting for the elements entering and leaving, we achieve O(n) time complexity instead of O(nk).

Time Complexity: O(n)

Space Complexity: O(1)

Solution in C++:

#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

int characterReplacement(string s, int k) {
    unordered_map<char, int> char_count;
    int left = 0;
    int max_count = 0;  // Maximum frequency in current window
    int max_length = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char_count[s[right]]++;
        max_count = max(max_count, char_count[s[right]]);
        
        // If window needs more than k replacements, shrink it
        // (window_size - max_frequency) = number of characters to replace
        if ((right - left + 1) - max_count > k) {
            char_count[s[left]]--;
            left++;
        }
        
        max_length = max(max_length, right - left + 1);
    }
    
    return max_length;
}

Step-by-Step Simulation:

Explanation: We use a sliding window approach. The key insight is that a valid window has at most k characters that are not the most frequent character. We track character frequencies and the maximum frequency in the current window. When (window_size - max_frequency) > k, we need to shrink the window. We maintain the maximum valid window length. Note: we don't need to update max_count when shrinking because we only care about the maximum we've seen, and a smaller window can't have a larger max_count.

Time Complexity: O(n)

Space Complexity: O(1) - at most 26 characters