Table of contents
- Q1. Solve the "maximum sum subarray of size k" problem.
- Q2. Solve the "longest substring without repeating characters" problem.
- Q3. Solve the "smallest window in a string containing all characters of another string" problem
- Q4. Solve the "find all anagrams of a string in another string" problem.
- Q5. Solve the "maximum number of vowels in a substring of length k" problem.
Today, I explored the sliding window technique to efficiently solve problems involving contiguous subarrays or substrings. I began by tackling the "maximum sum subarray of size k" problem, followed by solving the "longest substring without repeating characters" challenge. Then, I moved on to the "smallest window in a string containing all characters of another string" problem and implemented a solution to find all anagrams of a string within another string. Finally, I solved the "maximum number of vowels in a substring of length k" problem. These problems enhanced my ability to apply the sliding window technique to optimize solutions.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Solve the "maximum sum subarray of size k" problem.
#include <iostream>
using namespace std;
// Function to find the maximum sum subarray of size k
void max_sumsubarray_of_k(int arr[], int size, int k) {
int i = 0, j = k - 1;
int tempsum = 0;
// Calculate the sum of the first k elements
for (int l = 0; l <= j; l++) {
tempsum += arr[l];
}
int maxsum = tempsum; // Initialize the max sum
int start = 0; // Starting index of the subarray
// Slide the window across the array
for (int i = k; i < size; i++) {
tempsum = tempsum + arr[i] - arr[i - k]; // Slide the window by adding the next element and removing the previous one
if (tempsum > maxsum) { // Update maxsum if a new max is found
maxsum = tempsum;
start = i - k + 1; // Update the start index of the subarray
}
}
// Output the result
cout << "The max sum is: " << maxsum << endl;
int end = start + k - 1; // Ending index of the subarray
cout << "The subarray giving the sum is: [ ";
for (int i = start; i <= end; i++) {
cout << arr[i] << " "; // Print the elements of the subarray
}
cout << "]" << endl;
}
int main() {
int n, k;
cout << "Enter length of array: ";
cin >> n;
int arr[n];
cout << "Enter elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i]; // Input the array elements
}
cout << "Enter value of k: ";
cin >> k; // Input the size of the subarray
max_sumsubarray_of_k(arr, n, k); // Call the function to find the max sum subarray
return 0;
}
This code implements the sliding window technique to find the maximum sum of any subarray of size k in a given array. It first calculates the sum of the first k elements of the array. Then, it slides a window of size k across the array by adding the next element and subtracting the previous element from the sum (this keeps the window size constant). The code keeps track of the maximum sum encountered and the starting index of the subarray that yields this sum. Finally, it outputs the maximum sum along with the corresponding subarray. The sliding window technique ensures the solution runs in linear time, O(n), where n is the size of the array.
Q2. Solve the "longest substring without repeating characters" problem.
#include <iostream>
#include <vector>
using namespace std;
void longest_substring(string str) {
vector<int> dict(256, -1); // To store the last seen index of characters
int maxlength = 0, start = -1, begin = 0;
for (int i = 0; i < str.size(); i++) {
if (dict[str[i]] > start) {
start = dict[str[i]]; // Move the start to the position after the last occurrence
}
dict[str[i]] = i; // Update the last seen index of the character
if (maxlength < i - start) {
maxlength = i - start; // Update the maximum length
begin = start + 1; // Update the starting index of the longest substring
}
}
// Output the maximum length
cout << "Length of longest substring without repeating characters: " << maxlength << endl;
// Output the longest substring itself
cout << "Longest substring: ";
for (int i = begin; i < begin + maxlength; i++) {
cout << str[i];
}
cout << endl;
}
int main() {
string str;
cout << "Enter string: ";
getline(cin, str);
longest_substring(str);
return 0;
}
This code implements an algorithm to find the longest substring without repeating characters using the sliding window technique. It uses a vector dict of size 256 to store the last seen index of each character (assuming the character set is ASCII). The variable start tracks the starting index of the current window, and maxlength holds the length of the longest substring found so far. As the code iterates through the string, if a character is repeated within the current window (i.e., its last occurrence is after the current start), it updates start to the position right after the last occurrence of the repeating character. It then calculates the length of the current window and updates maxlength and the begin index if a longer substring is found. Finally, the code prints the length of the longest substring and the substring itself. The time complexity of this solution is O(n), where n is the length of the string.
Q3. Solve the "smallest window in a string containing all characters of another string" problem
#include <iostream>
#include <climits>
using namespace std;
string min_window_substring(string a, string b) {
if (b.empty() || a.empty()) return "";
int hash[256] = {0}; // To store the frequency of characters in b
for (char c : b) {
hash[c]++;
}
int required = 0; // Number of unique characters in b
for (int i = 0; i < 256; i++) {
if (hash[i] > 0) required++;
}
int left = 0, right = 0;
int formed = 0; // To track how many unique characters in b are matched
int window_count[256] = {0}; // To store the frequency of characters in current window
int min_length = INT_MAX, start = -1;
while (right < a.size()) {
char c = a[right];
window_count[c]++;
// If the current character's count matches the required count in b
if (hash[c] > 0 && window_count[c] == hash[c]) {
formed++;
}
// Try to contract the window until it ceases to be 'desirable'
while (left <= right && formed == required) {
c = a[left];
// Update minimum length and start position of the window
if (right - left + 1 < min_length) {
min_length = right - left + 1;
start = left;
}
// The character at position left is no longer a part of the window
window_count[c]--;
if (hash[c] > 0 && window_count[c] < hash[c]) {
formed--;
}
left++;
}
// Expand the window by moving right pointer
right++;
}
// If no valid window found, return empty string
return (start == -1) ? "" : a.substr(start, min_length);
}
int main() {
string a, b;
cout << "Enter first string: ";
getline(cin, a);
cout << "Enter second string: ";
getline(cin, b);
// Convert both strings to lower case for case insensitive comparison
for (char &c : a) c = tolower(c);
for (char &c : b) c = tolower(c);
string result = min_window_substring(a, b);
if (result.empty()) {
cout << "No valid window found." << endl;
}
else {
cout << "The smallest window is: " << result << endl;
}
return 0;
}
This code finds the smallest substring in string a that contains all characters of string b, including their frequencies. The algorithm uses the sliding window technique with two pointers (left and right) to dynamically adjust the window size while maintaining a count of characters in both a and b. It first initializes a frequency array hash[] to store the count of characters in b. The required variable tracks the number of unique characters in b. As the right pointer moves to expand the window, the window_count[] array keeps track of the frequency of characters in the current window. When the window contains all characters of b (i.e., formed == required), the left pointer is moved to shrink the window, updating the minimum length and starting index whenever a smaller valid window is found. Finally, the smallest window substring is returned, or an empty string is returned if no such window exists. The code also performs case-insensitive comparison by converting both strings to lowercase. The overall time complexity is O(n), where n is the length of string a.
Q4. Solve the "find all anagrams of a string in another string" problem.
#include <iostream>
using namespace std;
#include <vector>
// Function to find all starting indices of the anagrams of 'p' in string 's'
vector<int> find_anagram(string s, string p) {
vector<int> ans;
vector<int> hash(26, 0); // Frequency of characters in the current window of 's'
vector<int> phash(26, 0); // Frequency of characters in 'p'
int window = p.size(); // Size of the anagram string
int len = s.size(); // Length of the input string 's'
// If 's' is smaller than 'p', no anagram can exist
if (len < window) {
return ans;
}
int left = 0, right = 0;
// Initialize the frequency arrays for the first window of size 'window' in 's'
while (right < window) {
phash[p[right] - 'a'] += 1;
hash[s[right++] - 'a'] += 1;
}
right -= 1; // Adjust 'right' to the last index of the first window
// Slide the window across the string 's'
while (right < len) {
// If the frequency arrays match, it means an anagram is found
if (phash == hash) {
ans.push_back(left);
}
// Move the window to the right
right += 1;
if (right != len) {
hash[s[right] - 'a'] += 1; // Add the new character to the window
}
hash[s[left] - 'a'] -= 1; // Remove the character that is sliding out of the window
left += 1; // Shift the left pointer
}
return ans;
}
int main() {
string a, b;
cout << "Enter first string: ";
getline(cin, a); // Input first string 'a'
cout << "Enter second string: ";
getline(cin, b); // Input second string 'b'
// Find all starting indices of anagrams of 'b' in 'a'
vector<int> result = find_anagram(a, b);
// Output the result
for (int i = 0; i < result.size(); i++) {
cout << result[i] << " "; // Print each index where an anagram starts
}
return 0;
}
This code finds all the starting indices of anagrams of string p in string s. It uses the sliding window technique with two pointers (left and right) to efficiently check for anagrams. Initially, it compares the frequency of characters in the first window of size equal to p in s. It then slides the window across the string by moving the right pointer and adjusting the frequency of characters in the current window, while the left pointer is incremented to maintain the window size. If the frequency array of the current window matches the frequency array of p, it indicates that an anagram of p exists in that window, and the starting index (left) is recorded. The process continues until the entire string s has been checked. Finally, it outputs all the indices where an anagram of p starts in s. The time complexity of the algorithm is O(n), where n is the length of the string s, because each character is processed only once.
Q5. Solve the "maximum number of vowels in a substring of length k" problem.
#include <iostream>
using namespace std;
#include <bits/stdc++.h>
int countVowels(char c) {
c = tolower(c);
return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}
void find_max_vowels(string str, int k) {
int start = 0, max_count_of_vowels = 0, current_count = 0, index = 0;
// Count vowels in the first window of size k
for (int i = 0; i < k; i++) {
current_count += countVowels(str[i]);
}
max_count_of_vowels = current_count;
// Slide the window across the string
for (int end = k; end < str.length(); end++) {
// Add the vowel at the end of the window
current_count += countVowels(str[end]);
// Remove the vowel at the start of the window
current_count -= countVowels(str[start]);
// Update max vowels count and index
if (current_count > max_count_of_vowels) {
max_count_of_vowels = current_count;
index = start + 1;
}
// Move the window
start++;
}
cout << "The substring containing max no. of vowels is: " << str.substr(index, k) << endl;
}
int main() {
string str;
int k;
cout << "Enter the string: ";
getline(cin, str);
cout << "Enter value of k: ";
cin >> k;
find_max_vowels(str, k);
return 0;
}
This C++ code finds the substring of length k within a given string str that contains the maximum number of vowels. The program first defines a helper function countVowels to check if a character is a vowel (a, e, i, o, u) by converting the character to lowercase. The main function find_max_vowels calculates the number of vowels in the first substring of length k. Then, using the sliding window technique, it moves across the string, adjusting the count by adding the vowel at the end of the window and subtracting the vowel at the start. It tracks the substring with the highest vowel count and prints it. The program takes user input for the string and the window size k, then outputs the substring with the most vowels.
Today's practice solidified my understanding of the sliding window technique and its effectiveness in solving a variety of problems efficiently. From finding maximum sums and longest substrings to identifying anagrams and counting vowels, I gained valuable insights into how this technique can optimize time complexity. These exercises have equipped me with powerful tools to handle problems involving sequences and substrings. I'm excited to continue applying this technique to more complex challenges ahead!