C++ Coding Test Course, Sliding Window

C++ Coding Test Course: Sliding Window

Welcome! In this course, we will explore the popular algorithm technique known as Sliding Window.
The sliding window technique is frequently used when processing subsequences or subarrays in one-dimensional data structures such as arrays or strings.
It can greatly help in efficiently reducing complexity and solving problems.
In this post, we will explain the concept of sliding window and solve specific algorithm problems using it.

What is Sliding Window?

The sliding window technique involves setting a window of fixed size on an array or string and then moving that window from left to right during the exploration.
This technique efficiently navigates or calculates elements within the array, generally providing a significant advantage in reducing time complexity.
Sliding window can be broadly divided into two types:

  • Fixed Size Window: When the size of the window is fixed. For example, a problem that calculates the sum of K consecutive elements.
  • Variable Size Window: When the size of the window is variable. For example, a problem that finds the shortest subarray that satisfies a certain condition.

Problem Description: Longest Substring

The problem we will solve this time is as follows:
Find the length of the longest substring without repeating characters from a given string.
For example, when the input string is "abcabcbb", the output will be 3. (The longest substring is "abc".)

Approach to Solve the Problem

The sliding window is a suitable strategy for effectively solving this problem.
Here, we will use two pointers to check if there are any duplicate characters in the current window, and adjust the size of the window from both sides.
The main variables to be used in this approach are as follows:

  • left: The starting index of the window
  • right: The ending index of the window
  • max_length: The length of the longest substring
  • char_set: A set to store the characters in the current window

Algorithm Steps

  1. Initialize the left pointer left and the right pointer right to 0.
  2. Initialize the character set char_set.
  3. Move the right pointer right to the end of the string while performing the following:
    • If char_set already contains s[right], a duplicate has occurred, so increment the left pointer left to remove the duplicate.
    • If there are no duplicates, add s[right] to char_set.
    • Calculate the current window length right - left + 1 and compare it with max_length, updating it accordingly.
    • Increment the right pointer right.
  4. After exploring the entire string, return max_length.

C++ Code Implementation


#include <iostream>
#include <unordered_set>
#include <string>

using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_set char_set; // Character set of the current window
    int left = 0, max_length = 0;

    for (int right = 0; right < s.length(); ++right) {
        // Move the left pointer until no duplicate characters occur
        while (char_set.find(s[right]) != char_set.end()) {
            char_set.erase(s[left]);
            ++left;
        }
        // Add the current character
        char_set.insert(s[right]);
        // Update maximum length
        max_length = max(max_length, right - left + 1);
    }
    return max_length;
}

int main() {
    string s = "abcabcbb";
    cout << "Length of the longest substring: " << lengthOfLongestSubstring(s) << endl;
    return 0;
}

Code Explanation

In the above code, we use unordered_set to store the characters in the current window, and when a duplicate character occurs,
we move the left pointer to remove the duplicate. Each time we process a character, we update the maximum length.
This algorithm has a time complexity of O(n) when the length of the string is n.
This is because both pointers only pass through the string once.
The space complexity is O(min(n, m)), where n is the length of the string and m is the size of the character set.

Conclusion

In this post, we explored the process of solving the longest substring problem using the sliding window technique.
The sliding window is a powerful tool that can efficiently solve many problems, and it allows for a more effective approach to tackle algorithmic challenges.
In the next post, we will cover more algorithmic techniques and problems.
I hope this helps you in your coding test preparation!