How to Find the Longest Substring Without Repeating Characters in O(n)

Problem Statement

Given a string s, the task is to determine the length of the longest substring that contains no repeated characters. A substring is a contiguous sequence of characters within the string.

Example Cases

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

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

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

1. Brute‑Force Solution

The brute‑force approach checks every possible substring and verifies whether it contains duplicate characters.

Generate all possible substrings of the string.

For each substring, check if it contains any repeated character.

Record the maximum length among substrings that have all unique characters.

Implementation

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_length = 0
        for i in range(len(s)):
            for j in range(i + 1, len(s) + 1):
                substring = s[i:j]
                if len(substring) == len(set(substring)):
                    max_length = max(max_length, len(substring))
        return max_length

Time Complexity

The brute‑force method runs in O(n³) time because generating all substrings costs O(n²) and checking each substring for uniqueness can take up to O(n) in the worst case.

2. Optimized Solution (Sliding Window)

The sliding‑window technique finds the longest substring without repeating characters in linear time.

Maintain two pointers, left and right, representing the current window.

Move the right pointer to expand the window and add characters to a set.

If a character is already in the set, move the left pointer to shrink the window until the duplicate is removed.

During the process, keep track of the maximum window size observed.

Implementation

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()
        left = 0
        max_length = 0
        for right in range(len(s)):
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1
            char_set.add(s[right])
            max_length = max(max_length, right - left + 1)
        return max_length

Time Complexity

The sliding‑window algorithm runs in O(n) time because each character is processed at most twice—once by the right pointer and once by the left pointer.

Conclusion

Both approaches solve the longest‑substring‑without‑repeating‑characters problem, but the brute‑force method is inefficient for long inputs, while the sliding‑window technique provides an optimal linear‑time solution. Understanding these methods improves general problem‑solving skills for similar algorithmic challenges.