Sliding Window Technique in DSA (Longest Substring Without Repeating Characters)

Introduction

The Sliding Window Technique is one of the most important concepts in Data Structures and Algorithms (DSA). It is widely used to solve array and string problems efficiently.

A very popular interview problem based on this technique is Longest Substring Without Repeating Characters. This problem checks your understanding of strings, pointers, and hashing.

In this article, the material is explained in simple terms, making it easy for beginners to understand.

What is the Sliding Window Technique?

The Sliding Window Technique is used when we process continuous segments of an array or string.

Instead of recalculating values repeatedly, we maintain a window and slide it forward under specified conditions.

This technique helps reduce time complexity from slow approaches to faster ones.

Types of Sliding Windows

There are two common types of sliding windows:

Fixed Size Window – Window size remains constant
Variable Size Window – Window size changes based on conditions

The Longest Substring Without Repeating Characters uses a variable-size sliding window.

Problem Statement

Given a string, find the length of the longest substring that does not contain any repeating characters.

Example

Input: "abcabcbb"
Output: 3

Explanation

The longest substring without repeating characters is "abc", which has a length of 3.

Brute Force Approach (Not Efficient)

In the brute-force method, we check all possible substrings and verify whether they contain repeating characters.

Drawbacks

Too many substrings
Time Complexity becomes O(n²) or worse

This approach is not suitable for interviews.

Optimized Approach Using Sliding Window

To solve this problem efficiently, we use:

Two pointers (left and right)
A HashSet or HashMap to track characters

The idea is to expand the window until a duplicate character appears, then shrink the window.

Step-by-Step Explanation

Steps:

Initialize two pointers left and right
Use a set to store unique characters
Move right pointer forward
If character is already present, remove characters from the left
Update the maximum window size

This ensures all characters inside the window are unique.

Dry Run Example

String: "abcabcbb"

Left	Right	Window	Max Length
0	0	a	1
0	1	ab	2
0	2	abc	3
1	3	bca	3
2	4	cab	3
3	5	abc	3

Final Answer = 3

Code Implementation

C++ Code

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

    for (int right = 0; right < s.length(); right++) {
        while (set.find(s[right]) != set.end()) {
            set.erase(s[left]);
            left++;
        }
        set.insert(s[right]);
        maxLength = max(maxLength, right - left + 1);
    }
    return maxLength;
}

Java Code

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0, maxLength = 0;

    for (int right = 0; right < s.length(); right++) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(s.charAt(right));
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

Python Code

def lengthOfLongestSubstring(s):
    seen = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

Time and Space Complexity

Time Complexity: O(n)
Space Complexity: O(n)

The string is traversed only once, making the solution very efficient.

Edge Cases to Consider

Empty string
String with all same characters
String with spaces or special characters

Always test these cases during interviews.

Common Interview Variations

Longest substring with at most K distinct characters
Longest substring with no repeating characters
Smallest window containing all characters

These problems also use the sliding window technique.

Summary

The Sliding Window Technique is a powerful method for solving substring and subarray problems efficiently. In the Longest Substring Without Repeating Characters problem, it helps avoid unnecessary rechecking by maintaining a moving window. Once you understand this technique, many complex string and array problems become easy to solve. Mastering sliding window is essential for cracking DSA interviews.