Classic Interview 150 Problem P3: Longest Substring Without Repeating Characters

---

Timeline

Timeline

2025-11-11

init

Sliding window

---

Problem:

P3 Longest Substring Without Repeating Characters

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-interview-150

Sliding window; note the case where the entire string has no repeated characters.

#include <string>
#include <unordered_set>
#include <algorithm>
using std::string;
using std::unordered_set;

// Given a string s, find the length of the longest substring without repeating characters.
class Solution {
    public:
	int lengthOfLongestSubstring(string s)
	{
		int i = 0, j = 0;
		int n = s.size();
		unordered_set<char> uset;
		int len = 0;

		for (j = 0; j < n; j++) {
			if (uset.count(s[j])) {
				len = std::max(len, (int)uset.size());
				// Shrink the left boundary
				while (s[i] != s[j]) {
					uset.erase(s[i]);
					i++;
				}
				if (s[i] == s[j]) { //until the current character is removed
					uset.erase(s[i]);
					i++;
				}
			}
			uset.insert(s[j]);
		}
		return std::max(len, (int)uset.size());
	}
};

leetcode hot 100 rewrite:
Before entering the loop, shrink the left boundary first until the substring has no repeating characters.

#include <string>
#include <unordered_set>

using std::string;
using std::unordered_set;

class Solution {
    public:
        int lengthOfLongestSubstring(string s)
        {
                int left = 0, right, n = s.size();
                int max_len = 0;
                unordered_set<char> uset;

                if (n == 0)
                        return 0;

                for (right = 0; right < n; right++) { // left index of window

                        // shrink window
                        while (uset.count(s[right])) {
                                uset.erase(s[left]);
                                left++;
                        }

                        uset.insert(s[right]);

                        max_len = std::max(max_len, right - left + 1);
                }
                return max_len;
        }
};

Template approach:

#include <string>
#include <unordered_map>
using std::string;
using std::unordered_map;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0, right = 0, n = s.size();
        int max_len = 0;
        unordered_map<char, int> umap;

        // abcabcbb
        while (right < n) {
            umap[s[right]]++;
            right++;

            while (umap[s[right - 1]] > 1) {
                umap[s[left]]--;
                left++;
            }
            max_len = std::max(max_len, right - left);
        }

        return max_len;
    }
};