Data Structures and Algorithms (DSA)  

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:

  1. Initialize two pointers left and right

  2. Use a set to store unique characters

  3. Move right pointer forward

  4. If character is already present, remove characters from the left

  5. Update the maximum window size

This ensures all characters inside the window are unique.

Dry Run Example

String: "abcabcbb"

LeftRightWindowMax Length
00a1
01ab2
02abc3
13bca3
24cab3
35abc3

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.

Membership not found