Longest Substring Without Repeating Characters - Sliding Window - Visualization

Sliding Window & Two Pointer Problems

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given a string s, your task is to find the length of the longest substring that contains no repeating characters.

If the string is empty, return 0.

For example:

Input: s = "abcabcbb" → Output: 3 (The answer is "abc")

Examples❯

s Output Description
"abcabcbb" 3 "abc" is the longest substring without repeating characters.
"bbbbb" 1 All characters are the same. Longest substring is "b".
"pwwkew" 3 Longest substring is "wke" with no repeating characters.
"abcdefg" 7 All characters are unique. Entire string is the longest substring.
"aab" 2 Longest substring is "ab" after skipping the second 'a'.
"dvdf" 3 "vdf" is the longest substring without repeating characters.
"tmmzuxt" 5 Longest substring is "mzuxt".
"anviaj" 5 Longest substring is "nviaj".
"a" 1 Single character string. Only one character, so answer is 1.
"" 0 Empty string has no characters. Answer is 0.

Solution❯

Understanding the Problem

We are given a string s, and our goal is to find the length of the longest substring that contains no repeating characters. A substring is a contiguous block of characters from the string, and "no repeating characters" means each character must appear only once in that block.

For example, in the string "abcabcbb", the longest such substring is "abc", which has a length of 3.

This is a common sliding window problem — a technique that lets us move through the string efficiently while maintaining a valid "window" of non-repeating characters.

Step-by-Step Solution with Example

Step 1: Initialize variables

We use two pointers: start to indicate the start of the current window and i to iterate through the string.

We also use a map called charIndexMap to store the most recent index of each character we've seen.

We initialize maxLen = 0 to store the length of the longest substring found.

Step 2: Traverse the string

Start with the example: s = "abcabcbb"

  • Start with start = 0, maxLen = 0
  • At i = 0: character is 'a' → not seen before → update map: {a: 0}, window is "a" → maxLen = 1
  • At i = 1: character is 'b' → not seen before → map: {a: 0, b: 1}, window: "ab" → maxLen = 2
  • At i = 2: character is 'c' → not seen → map: {a: 0, b: 1, c: 2}, window: "abc" → maxLen = 3
  • At i = 3: character is 'a' → seen at index 0, which is ≥ start (0) → update start = 1 → map: {a: 3, b: 1, c: 2}, window: "bca"
  • At i = 4: character is 'b' → seen at index 1, which is ≥ start (1) → update start = 2 → map: {a: 3, b: 4, c: 2}, window: "cab"
  • At i = 5: character is 'c' → seen at index 2 → update start = 3 → map: {a: 3, b: 4, c: 5}, window: "abc"
  • At i = 6: character is 'b' → seen at index 4 → update start = 5 → map: {a: 3, b: 6, c: 5}, window: "cb"
  • At i = 7: character is 'b' → seen at index 6 → update start = 7 → map: {a: 3, b: 7, c: 5}, window: "b"

Throughout this process, the maximum length of a window with all unique characters we saw was 3.

Step 3: Return the result

After processing all characters, return maxLen which holds the length of the longest valid substring.

Edge Cases

  • Empty string: If s = "", there are no characters, so return 0.
  • All same characters: If s = "aaaa", the longest substring without repeating characters is "a", so return 1.
  • All unique characters: If s = "abcdef", no character repeats, so return the length of the whole string → 6.
  • String with spaces or symbols: Spaces and symbols are also treated as characters, so "a b c a b" would be processed similarly.

Final Thoughts

This problem is efficiently solved using the sliding window technique. It avoids nested loops by adjusting the window dynamically as we encounter repeating characters, resulting in a time complexity of O(n).

By using a map to store the last seen index of each character, we ensure we always know where to move the window's start. This approach is beginner-friendly once you understand the idea of a window sliding over the string and adjusting as needed to maintain uniqueness.

Algorithm Steps❯

  1. Initialize a hash set or map charIndexMap to track characters and their most recent indices.
  2. Use two pointers: start for the beginning of the current window, and i for the current character index.
  3. Initialize maxLen = 0 to store the length of the longest valid substring.
  4. Traverse the string using index i from 0 to end of string:
  5. → If s[i] is already in charIndexMap and its last index is ≥ start, update start = charIndexMap[s[i]] + 1.
  6. → Update or insert s[i] in charIndexMap with the current index i.
  7. → Update maxLen = max(maxLen, i - start + 1).
  8. After the loop ends, return maxLen as the final answer.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <string.h>

int lengthOfLongestSubstring(char* s) {
    int lastIndex[256];
    for (int i = 0; i < 256; i++) lastIndex[i] = -1;

    int maxLen = 0, start = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        unsigned char ch = s[i];
        if (lastIndex[ch] >= start) {
            start = lastIndex[ch] + 1;
        }
        lastIndex[ch] = i;
        int windowLen = i - start + 1;
        if (windowLen > maxLen) maxLen = windowLen;
    }
    return maxLen;
}

int main() {
    char s[] = "abcabcbb";
    int result = lengthOfLongestSubstring(s);
    printf("Length of longest substring without repeating characters: %d\n", result);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)In the best case, where all characters are unique, the algorithm still needs to traverse each character once, updating the map and window size. Thus, the time complexity remains linear.
Average CaseO(n)Each character is processed at most twice: once when added to the hash map and possibly again when the window start is moved. Hence, the total operations are proportional to the string length.
Worst CaseO(n)In the worst case, such as when the string contains all unique characters or repeated patterns forcing frequent updates to the start pointer, each character is still visited at most twice, making the time complexity linear.

Space Complexity❯

O(min(n, m))

Explanation: The hash map stores at most 'm' unique characters, where 'm' is the size of the character set (e.g., 26 for lowercase letters, 128 for ASCII). In the worst case, it stores all 'n' characters of the string if they are all unique. Hence, the space complexity is O(min(n, m)).


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...