Problem Overview

  • We are given a string s.
  • Our goal is to find the longest substring that does not contain repeating characters.
  • In other words, the length of the substring should equal the number of unique characters in it.
  • If found → return the length, otherwise → return 0.
  • There can be multiple valid substring of length

LeetCode - Longest Substring Without Repeating Characters

A substring is continous part of string. The string itself is a valid substring.

Example

Input:  s = "abcabcbb"
Output: 3

Explanation: "abc" is the longest substring without repeating characters.

Brute Force

Intuition

  • We try to generate all possible substrings.
  • Use a hashmap to keep track of the count of characters seen in the current substring.
  • If a character is encountered twice, reject that substring and move on.
  • We keep track of length of an valid sub string.

Code

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        int n = s.size();
        int result = 0;
        unordered_map<char, int> mp;
        int len = 0;

        for (int i = 0; i < n; i++) {

            for (int j = i; j < n; j++) {

                if (mp.count(s[j])) {
                    break;
                }

                len++;
                mp[s[j]]++;
                result = max(result, len);
            }

            mp.clear();
            len = 0;
        }

        return result;
    }
};

Complexity

  • Time: O(n²) — two nested loops over the string
  • Space: O(n)

Optimal Solution — Sliding Window

Intuition

  • Instead of checking all combinations like brute force, we can reduce it using a sliding window.
  • We start from index 0 with both pointers i and j.
  • We move j forward while checking if any element is repeated in the map.
  • If a repeated element is found, we move i forward while decrementing the cout of that number in the map.
  • At every step when j moves ahead, we check for the maximum window length.

This problem is combination of Sliding Window and Hashmap.

Edge Case

When the value of char in map becomes zero we remove it, because the mp.count(s[j]) return true, even though character is not present.

Code

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        int n = s.size();
        int result = 0;
        unordered_map<char, int> mp;

        int i = 0, j = 0;

        while (i < n && j < n) {
            if (mp.count(s[j])) {
                mp[s[i]]--;
                if (mp[s[i]] == 0) {
                    mp.erase(s[i]);
                }
                i++;
                continue;
            }

            mp[s[j]]++;
            j++;
            result = max(result, (j - i));
        }

        return result;
    }
};

Further Optimized Version

What We Improve

  1. Index Storage Instead of Count

    • Instead of storing the count of each character, store the last seen index.
    • When a repeated character is found, jump i directly to max(i, lastIndex + 1).
    • This avoids unnecessarily shrinking the window one step at a time.

  2. Eliminates Redundant Shrinking

    • In the previous approach, i moves one step per iteration even when it could skip ahead.
    • With index storage, we skip directly past the duplicate — reducing iterations significantly.

Optimized Code

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        int n = s.size();
        int result = 0;
        unordered_map<char, int> mp;

        int i = 0, j = 0;

        while (i < n && j < n) {
            if (mp.count(s[j]))
                i = max(i, mp[s[j]] + 1);

            mp[s[j]] = j;
            j++;
            result = max(result, (j - i));
        }

        return result;
    }
};

Time and Space Complexity

  • Time: O(n)

    • Each character is visited at most twice (once by j, skipped by i).
    • With index optimization, even fewer operations in practice.

  • Space: O(n)

Final Takeaways

  • Always break the problem into smaller sub problems.
  • In sliding window, always think about when to expand and when to shrink the window.
  • In two pointer you need to figure out when to move both points in same or opposite direction.
  • Storing the last index instead of count is a powerful trick to avoid redundant pointer movement.
  • String + unique characters → Think Sliding Window + Hashmap first.