Day 16: 100 Days of DSA

Welcome to Day 16 of my 100 Days of DSA challenge! Today, I solved five problems focused on sliding window technique. Here's a quick look at the questions I tackled and how I approached them 🤖✨ Check out my GitHub repository for all my solutions and progress. Let’s keep learning!

The sliding window technique is a simple yet powerful way to process a contiguous subset of elements in a larger dataset (like an array or string). Instead of repeatedly recalculating values for overlapping parts of the subset, the window "slides" across the data, reusing calculations from the previous step.

Think of it as having a physical window that you slide over a line of items, one step at a time, while updating information dynamically as the window moves.

Key Idea of Sliding Window

For each new step:

1. Add the new element entering the window.

2. Remove the element leaving the window (if fixed size).

3. Update the result (e.g., max/min sum, longest substring, etc.).

Let’s see the problems and their code.

1. Solve the "maximum sum subarray of size k" problem.

Use the sliding window technique to calculate the sum of the first k elements. Then slide the window across the array by adding the next element and removing the first element of the previous window, updating the maximum sum dynamically.

Code:

// To find maximum subarray of length 'k' in an array

#include<vector>
#include<iostream>
using namespace std;

void display(vector<int> nums,int start,int k){
    for(int i=start;i<start+k;i++){
        cout<<nums[i]<<" ";
    }
    cout<<endl;
}

void maxSubArray(vector<int> prices,int k){

    int sum=0,maxPrice=0,start=0;

    // finding the sum of first k elements
    for(int i=0;i<k;i++){
        sum+=prices[i];
    }

    maxPrice=sum;

    // finding the max subarray using sliding window
    for(int i=k;i<prices.size();i++){
        sum+=prices[i]-prices[i-k];
        if(sum>maxPrice){
            maxPrice=sum;
            start=i-k+1;
        }
    }

    display(prices,start,k);
    cout<<"The maximum subarray sum is:"<<maxPrice<<endl; 
}

int main(){
    vector<int> prices={2,3,4,5,6,7,7,8,9};
    cout<<"The array is:"<<endl;
    for(int i=0;i<prices.size();i++){
        cout<<prices[i]<<" ";
    }
    cout<<endl;
    int k=4;
    cout<<"Max sum subarray:"<<endl;
    maxSubArray(prices,k);
}

Output:

2. Solve the "longest substring without repeating characters" problem.

Maintain a sliding window of unique characters using a set or map. Expand the window until a duplicate character is found, then shrink it from the left while maintaining uniqueness. Keep track of the maximum length.

Code:

// To find the longest substring without repeating characters

#include<iostream>
#include<bits/stdc++.h>
#include <unordered_set>
using namespace std;

int longSubStr(string s){
    int left=0,maxLen=0;
    unordered_set<char> set;

    for(int right=0;right<s.size();right++){
        while(set.find(s[right])!=set.end()){
            set.erase(s[left]);
            left++;
        }

        set.insert(s[right]);
        maxLen=max(maxLen,right-left+1);
    }

    return maxLen;
}
int main(){
    string s="abcabcbb";
    cout << "Longest substring without repeating characters: " << longSubStr(s) << endl;
    return 0;
}

Output:

3. Solve the "smallest window in a string containing all characters of another string" problem.

Use two pointers with a sliding window to expand and shrink the window. Maintain a frequency map of required characters and match counts. Adjust the window to minimize its size while containing all required characters.

Code:

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

string smallestWindow(string s, string t) {
    if (t.size() > s.size()) return "-1";

    unordered_map<char, int> target_freq, window_freq;
    for (char ch : t) {
        target_freq[ch]++;
    }

    int start = 0, min_length = INT_MAX, min_start = 0, matched = 0;

    for (int end = 0; end < s.size(); end++) {
        char right_char = s[end];
        window_freq[right_char]++;

        if (target_freq.find(right_char) != target_freq.end() && 
            window_freq[right_char] <= target_freq[right_char]) {
            matched++;
        }

        while (matched == t.size()) {
            if (end - start + 1 < min_length) {
                min_length = end - start + 1;
                min_start = start;
            }

            char left_char = s[start];
            window_freq[left_char]--;
            if (target_freq.find(left_char) != target_freq.end() && 
                window_freq[left_char] < target_freq[left_char]) {
                matched--;
            }
            start++;
        }
    }

    return min_length == INT_MAX ? "-1" : s.substr(min_start, min_length);
}

int main() {
    string s = "ADOBECODEBANC";
    string t = "ABC";

    string result = smallestWindow(s, t);
    cout << "Smallest window: " << result << endl;

    return 0;
}

Output:

4. Solve the "find all anagrams of a string in another string" problem.

Use a frequency map to compare the character counts of the target string and the current window. Slide the window across the source string, updating the counts, and check for matches at each step.

Code:

// To find all anagrams of a string in another string problem.

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> findAnagrams(string s, string p) {
    vector<int> result;
    int len_s = s.length(), len_p = p.length();

    if (len_p > len_s) return result;

    unordered_map<char, int> p_count;
    for (char ch : p) {
        p_count[ch]++;
    }

    unordered_map<char, int> s_count;

    for (int i = 0; i < len_p; ++i) {
        s_count[s[i]]++;
    }

    if (s_count == p_count) {
        result.push_back(0);
    }

    for (int i = len_p; i < len_s; ++i) {
        s_count[s[i]]++;
        s_count[s[i - len_p]]--;

        if (s_count[s[i - len_p]] == 0) {
            s_count.erase(s[i - len_p]);
        }

        if (s_count == p_count) {
            result.push_back(i - len_p + 1);
        }
    }

    return result;
}

int main() {
    string s = "cbaebabacd";
    string p = "abc";

    vector<int> result = findAnagrams(s, p);

    cout << "Anagram indices: ";
    for (int index : result) {
        cout << index << " ";
    }
    cout << endl;

    return 0;
}

Output:

5. Solve the "maximum number of vowels in a substring of length k" problem.

Use a sliding window to count vowels in the first k characters. Slide the window, adding the next character and removing the first one, while updating the maximum vowel count.

Code:

// To find the maximum number of vowels in a substring of size k

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int maxNoOfVowels(string s,int k){
    int maxVowelCount=0,vowelCount=0;
    for(int i=0;i<k;i++){
        if(s[i]=='a' || s[i]=='e' || s[i]=='i' || s[i]=='o' || s[i]=='u'){
            vowelCount+=1;
        }
    }

    maxVowelCount=vowelCount;

    for(int i=k;i<s.size();i++){
        if(s[i]=='a' || s[i]=='e' || s[i]=='i' || s[i]=='o' || s[i]=='u'){
            vowelCount+=1;
        }

         if(s[i-k]=='a' || s[i-k]=='e' || s[i-k]=='i' || s[i-k]=='o' || s[i-k]=='u'){
            vowelCount-=1;
        }
    }

    maxVowelCount=max(maxVowelCount,vowelCount);
    return maxVowelCount;

}

int main(){
    string s = "aeiouaeiou";
    int k = 5;
    cout << "Max vowels in a substring of length " << k << " is: " << maxNoOfVowels(s, k) << endl;
    return 0;
}

Output:

This is all for today! Happy Coding!