LeetCode 3. Longest Substring Without Repeating Characters

The difference between Substring and Subsequence:

• Substring should be consecutive

• Subsequence doesn’t have to be consecutive

For example,

In ABCD and ACD

‘ACD’ is the subsequence of both strings, and only ‘A’ is the substring.

Brainstorming Thinking Process

I will solve this problem using DP.

There can be two approaches:

1. Find all the substrings, and eliminate all the strings which have duplicate characters.

2. Eliminate duplicate characters from the beginning.

Method 1 seems to be easier than the other.

…No, Method 2. Because Method 1 can be meaningless. I need to compare only two consecutive characters and repeat all the strings and check if there are duplicate characters, which will eliminate almost all of the strings, and that’s very inefficient.

Do I need two pointers to solve?

I will take the same process as regular LCS problem, but I need to iteratively check whether each iteration has duplicate characters or not.

I said I need to repeat each step iteratively, but can I solve it in DP?

Final method

I need two pointers and one sub pointer:

• stat starts from the beginning of the string

• sub scans the characters from stat to i-1, and if s[sub] and s[i] are the same, stat changes to sub + 1

• i iterates from the beginning to the end

Return value is i - stat + 1.

Here is the pseudo code:

for (sub: stat ~ i-1): 
    if character at sub is same as charater at i:
        move stat pointer to the next character 

    result: max(previous result, i - stat + 1)

My Answer:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        i = 0
        stat = 0
        result = 1
        size = len(s)

        if size == 0: 
            return 0

        for i in range(size): 

            for sub in range(stat, i):
                if s[sub] == s[i]: 
                    stat = sub + 1

            result = max(result, i - stat + 1)

        return result

Time Complexity: O(n²)

Why Wrong Answers?

I had to think of size = 0 cases and empty strings. Also I should have put the code ‘result = max(result, i - stat + 1) ‘ inside the outer loop, not inside the if statement in the inner loop.

Solution: Oops.. I need to subscribe LeetCode premium to see the solution! I asked gemini about the optimum solution.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_map = {}  # Stores the last seen index of each character
        start = 0      # Left boundary of the window
        max_length = 0

        for end in range(len(s)):
            # If we find a repeating character within the current window
            if s[end] in char_map and char_map[s[end]] >= start:
                # Move the 'start' pointer to skip the duplicate
                start = char_map[s[end]] + 1

            # Update the character's last seen index
            char_map[s[end]] = end

            # Calculate the window size and update max_length
            max_length = max(max_length, end - start + 1)

        return max_lengthThe difference of substring and subsequence is this:

• Your $O(n^2)$ Code: When you find a duplicate, your inner loop (for sub in range...) manually scans the previous characters to find where the duplicate was. This is like looking for a specific page in a book by flipping through every single page from the beginning every time.

• Optimized $O(n)$ Code: The Hash Map (char_map) acts like an index at the back of the book. It tells you exactly which index the character is at in $O(1)$ (constant time). You don't "search"; you "lookup."