JavaScript Coding Test Course, Sliding Window

1. What is Sliding Window?

The Sliding Window technique is an algorithmic approach used to find a subarray or substring that meets specific conditions in a given array or list. It is primarily suitable for problems that require consecutive elements and can use either a fixed-size or variable-size window depending on the problem.

1.1 Advantages of Sliding Window

The biggest advantage of the sliding window is that it can significantly reduce time complexity compared to the brute force method. It is often possible to reduce from O(n^2) to O(n). The sliding window uses two pointers to traverse the array, enabling efficient access.

2. Example Algorithm Problem

Problem: Maximum Length of Repeating Character Replacement

Given a string, write a function that returns the length of the longest substring that can be created by changing at most ‘k’ characters.


    Example:
    Input: s = "AABABBA", k = 1
    Output: 4
    Explanation: The characters that can be changed are 'A' or 'B'. You can change two 'B's to 'A' to make 'AAAA'.

Approach to the Problem

You can use a sliding window to solve this problem. Here, we will count the number of characters present in the current window and check if we can replace ‘k’ characters.

2.1 Steps of the Algorithm

  1. Initialize the left pointer and the right pointer.
  2. Use a HashMap to count the characters in the substring.
  3. Check the validity of the current window.
  4. If invalid, move the left pointer.
  5. Record the current window size and move the right pointer.
  6. Repeat this process to find the maximum length.

3. Code Implementation

Below is the JavaScript code based on the algorithm described above.


    function characterReplacement(s, k) {
        const countMap = {};
        let left = 0;
        let maxLength = 0;
        let maxCount = 0;

        for (let right = 0; right < s.length; right++) {
            countMap[s[right]] = (countMap[s[right]] || 0) + 1;
            maxCount = Math.max(maxCount, countMap[s[right]]);

            while (right - left + 1 - maxCount > k) {
                countMap[s[left]]--;
                left++;
            }

            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    // Example usage
    console.log(characterReplacement("AABABBA", 1)); // 4

4. Code Explanation

In the above code, we are processing the string ‘s’ in relation to the given ‘k’ repeatedly. We use countMap to count the frequency of each character, and we track the number of the most frequent character in the current window.

4.1 Explanation of Key Variables

  • countMap: An object that counts the occurrences of each character
  • left: The left boundary of the window
  • maxLength: Stores the maximum length
  • maxCount: The number of the most frequent character in the current window

4.2 Movement of the Sliding Window

The right pointer increases and moves to the end of the string while the left pointer only moves when the current window is invalid. The valid condition is that the number of most frequent characters subtracted from the current window size must be less than or equal to ‘k’. This checks whether specific characters can be replaced.

5. Time Complexity and Space Complexity

The time complexity of this algorithm is O(n). It traverses each character of the string only once, and the space complexity is O(1) because it only needs to store 26 letters due to considering only uppercase alphabet letters.

6. Various Problem-Solving Methods

The sliding window technique can be applied in many diverse ways. Thus, mastering this concept will help in solving many other algorithm problems. For example:

  • Maximum number of consecutive 1’s problem
  • Minimum-length subarray sum problem
  • Finding all anagrams problem

6.1 Additional Example Problem

The following problem can also be efficiently solved using the sliding window:


    Problem: Shortest subarray sum case
    Find the minimum length of the subarray that sums up to a specific number in the given array.

7. Conclusion

In this lecture, we covered the basic concept of the sliding window technique and solved an algorithm problem using it. This technique is particularly useful for string processing and subarray-related problems, so practice and familiarize yourself to tackle various variations of problems effectively.

Mastering the sliding window pattern can significantly reduce the difficulty of algorithm problems, and it often appears in coding tests in companies. I hope you acquire this technique perfectly through ample practice in the future.

8. Additional Resources

If you want to solve more sliding window problems, you can find numerous problems on online platforms such as LeetCode and HackerRank.