📘 LeetCode 3: Longest Substring Without Repeating Characters
📌 LeetCode: 3.Longest-Substring-Without-Repeating-Characters
📋 Problem Statement
title: “LeetCode 3: Longest Substring Without Repeating Characters — Engineering & Algorithmic Solution Note” problem_number: 3 problem_name: “Longest Substring Without Repeating Characters” difficulty: “Medium” category: “dsa_solutions” tags: [leetcode-3, longest-substring, sliding-window, hash-set, two-pointers, string, medium, csharp, dotnet9, dsa, problem-solving, leetcode, learning-note]
📘 LeetCode 3: Longest Substring Without Repeating Characters
📌 Connected Resource Graph
- 🟢 Primary Theory Note: 04_sliding_window_maximum_minimum_fixed_variable.md
- 🟡 Hash Tables & Sets: 00_overview_hash_tables_dictionary_hashmap.md
- 📂 Local Project Companion Files:
- 💻
Program.cs - ⚡
complexity.md - 🚨
tips.md
- 💻
1. 🎯 Problem Statement & Constraints
Given a string s, find the length of the longest substring without repeating characters.
Examples
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.Constraints
sconsists of English letters, digits, symbols and spaces.
2. 💡 Optimal Implementation (C# Sliding Window)
public static int LengthOfLongestSubstring(string s)
{
if (string.IsNullOrEmpty(s)) return 0;
var charIndexMap = new Dictionary<char, int>();
int maxLength = 0;
int left = 0;
for (int right = 0; right < s.Length; right++)
{
char c = s[right];
if (charIndexMap.TryGetValue(c, out int lastIndex) && lastIndex >= left)
{
left = lastIndex + 1; // Jump left pointer past last duplicate
}
charIndexMap[c] = right;
maxLength = Math.Max(maxLength, right - left + 1);
}
return maxLength;
}💡 Multi-Solution Analysis
title: “Complexity Analysis — LeetCode 3: Longest Substring Without Repeating Characters” tags: [leetcode-3, longest-substring, complexity, big-o, sliding-window, dsa, problem-solving, leetcode, learning-note]
⚡ Complexity Analysis — LeetCode 3: Longest Substring Without Repeating Characters
1. Asymptotic Comparison Matrix
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force (Substrings + Set Check) | Extremely slow, TLE | ||
Basic Sliding Window (left++) | Each character visited at most twice | ||
| Optimized Sliding Window (Index Jump) | Optimal: left jumps directly to lastIndex + 1 |
where is the alphabet size (ASCII or 256).