LeetCode Problem 3 - Longest Substring Without Repeating Characters

Problem Statement (LeetCode 3)

Given a string s, find the length of the longest substring without repeating characters.

Example Input & Output

Example 1

Input: s = "abcabcbb"
Output: 3
Explanation: The longest substring without repeating characters is "abc", which has length 3.

Example 2

Input: s = "bbbbb"
Output: 1
Explanation: The longest substring without repeating characters is "b", which has length 1.

Example 3

Input: s = "pwwkew"
Output: 3
Explanation: The longest substring without repeating characters is "wke", which has length 3.

---

Optimal Approach: Sliding Window with HashMap

To solve this problem optimally, we use the Sliding Window + HashMap approach. This method efficiently tracks unique characters within a window.

Steps to Solve

1. Use two pointers (left and right) to represent the current window.
2. Use a hashmap (unordered_map in C++) to store the last index of each character.
3. Expand the window (right++) until a repeating character is found.
4. If a character is repeated, move left to one position after the last occurrence of that character.
5. Keep track of the maximum length found during traversal.
6. Continue until right reaches the end of the string.

Time Complexity

• O(n) → We traverse the string once using the right pointer, and left moves only forward.
• O(1) Space Complexity → The hashmap stores at most 26 (lowercase letters) or 128 (ASCII characters).

---

LeetCode-Compatible C++ Code

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> charIndex; // Stores last index of characters
        int left = 0, maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            char currentChar = s[right];

            // If character is repeated, move left pointer
            if (charIndex.find(currentChar) != charIndex.end() && charIndex[currentChar] >= left) {
                left = charIndex[currentChar] + 1;
            }

            // Store/update index of current character
            charIndex[currentChar] = right;

            // Update max length
            maxLength = max(maxLength, right - left + 1);
        }

        return maxLength;
    }
};

---

Step-by-Step Explanation

Initialization

• unordered_map<char, int> charIndex → Stores the last seen index of each character.
• left = 0 → Left boundary of the sliding window.
• maxLength = 0 → Stores the maximum substring length.

Processing Each Character

1. If a character repeats within the window, move the left pointer just after the last occurrence.
2. Update the hashmap with the latest index of the character.
3. Update max length using max(right - left + 1).

---

Dry Run

Example: "abcabcbb"

Step	Left (l)	Right (r)	Char	Action	HashMap (charIndex)	Max Length
1	0	0	'a'	Add	{a: 0}	1
2	0	1	'b'	Add	{a: 0, b: 1}	2
3	0	2	'c'	Add	{a: 0, b: 1, c: 2}	3
4	0 → 1	3	'a'	Move left to 1	{a: 3, b: 1, c: 2}	3
5	1 → 2	4	'b'	Move left to 2	{a: 3, b: 4, c: 2}	3
6	2 → 3	5	'c'	Move left to 3	{a: 3, b: 4, c: 5}	3
7	3	6	'b'	Update	{a: 3, b: 6, c: 5}	3
8	4	7	'b'	Update	{a: 3, b: 7, c: 5}	3

Final Result: 3 (Substring: "abc")

---

Alternative Approaches & Why Not?

1. Brute Force (Nested Loops)

• Idea: Try all substrings, check for uniqueness.
• Time Complexity: O(n²) (Too slow)
• Space Complexity: O(n) for storing unique characters.

2. Sorting + Sliding Window

• Idea: Sort characters first, then find the longest non-repeating substring.
• Time Complexity: O(n log n) (Sorting overhead)
• Why Not? Sorting disrupts original order.

3. Two Pointers without HashMap

• Idea: Instead of a hashmap, use an array of size 128.
• Time Complexity: O(n)
• Space Complexity: O(1)
• When to Use? If characters are limited to ASCII.

---

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Sliding Window (Best)	O(n)	O(1)	Efficient
Brute Force	O(n²)	O(n)	Too slow
Sorting + Sliding Window	O(n log n)	O(n)	Unnecessary sorting
Two Pointers + Array	O(n)	O(1)	Works for ASCII

---

Conclusion

• The Sliding Window with HashMap approach is the best solution with O(n) time complexity.
• Alternative Approaches like brute force are inefficient for large inputs.
• Space Complexity remains O(1) since we use a fixed-sized hashmap (128 ASCII characters).

Recommended Problems for Practice

1. Longest Repeating Character Replacement
2. Minimum Window Substring
3. Longest Palindromic Substring

By mastering these problems, you'll improve your sliding window technique and string manipulation skills! 🚀