Longest Substring Without Repeating Characters

Q: What is the best time complexity for Longest Substring Without Repeating Characters?

Optimal (sliding window with last-seen index) runs in O(n) time and O(k) extra space. One pass, O(1) work per character.

Q: Which pattern does Longest Substring Without Repeating Characters use?

It is a arrays & hashing problem that uses the sliding window · variable pattern. Other problems with the same pattern: Minimum Size Subarray Sum, Count of Subarrays with Product Less Than K, Longest Repeating Character Replacement.

Q: Is there a brute force solution for Longest Substring Without Repeating Characters?

Yes. Brute force takes O(n²) time and O(k) space. Try every start index.

Q: Which edge cases should I test for Longest Substring Without Repeating Characters?

Empty string; All characters the same; All characters different: the answer is the whole length; A repeat far behind the current window, like "abba", must not move the window start backwards; Spaces and symbols count as characters too.

Medium Arrays & Hashing Sliding Window · Variable Original on LeetCode

Reported atAmazon Netflix Adobe Flipkart

Longest Substring Without Repeating Characters is a medium arrays & hashing problem solved with the sliding window · variable pattern. The best approach, optimal (sliding window with last-seen index), runs in O(n) time and O(k) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

Given a string s, return the length of the longest substring in which no character appears more than once.

A substring is a contiguous run of characters, so "pqs" is not a substring of "pqrs".

Examples

Example 1

Input: s = "pqrpqst"
Output: 5
Why: "rpqst" (indices 2 to 6) has no repeated character, and every longer window repeats p or q.

Example 2

Input: s = "zzzz"
Output: 1
Why: Any window longer than one character contains two z's.

Example 3

Input: s = ""
Output: 0
Why: An empty string has only the empty substring.

Constraints

0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols and spaces (ASCII).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force	`O(n²)`	`O(k)`
Better (sliding window with a set)	`O(n)`	`O(k)`
Optimal (sliding window with last-seen index)	`O(n)`	`O(k)`

1Brute force

TimeO(n²)Up to n starts, and each extends up to n characters (in practice at most k, the alphabet size).

SpaceO(k)The set holds at most k distinct characters (k <= 128 here).

Try every start index. From each start, extend the window one character at a time while keeping a set of what is inside; stop at the first repeat. The longest run found from any start is the answer.

For each start i, create an empty set.
For j = i, i + 1, …: if s[j] is in the set, stop; otherwise add it and update best with j - i + 1.
Return best.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int best = 0;
        for (int i = 0; i < n; i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                if (seen.contains(c)) break;
                seen.add(c);
                best = Math.max(best, j - i + 1);
            }
        }
        return best;
    }
}

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        best = 0
        for i in range(n):
            seen = set()
            for j in range(i, n):
                if s[j] in seen:
                    break
                seen.add(s[j])
                best = max(best, j - i + 1)
        return best

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int best = 0;
        for (int i = 0; i < n; i++) {
            unordered_set<char> seen;
            for (int j = i; j < n; j++) {
                if (seen.count(s[j])) break;
                seen.insert(s[j]);
                best = max(best, j - i + 1);
            }
        }
        return best;
    }
};

function lengthOfLongestSubstring(s) {
    const n = s.length;
    let best = 0;
    for (let i = 0; i < n; i++) {
        const seen = new Set();
        for (let j = i; j < n; j++) {
            if (seen.has(s[j])) break;
            seen.add(s[j]);
            best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

2Better (sliding window with a set)

TimeO(n)Each index is added once and removed at most once, so both pointers move at most n times.

SpaceO(k)The set holds the window's distinct characters, at most k.

Keep a window [l, r] with no repeats and a set of its characters. Move r forward one step at a time. If s[r] is already in the set, remove characters from the left until it is gone, then add s[r]. The window never moves backwards, so every character enters and leaves at most once.

Set l = 0 and an empty set.
For each r: while s[r] is in the set, remove s[l] and increase l.
Add s[r] and update best with r - l + 1.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> window = new HashSet<>();
        int l = 0, best = 0;
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            while (window.contains(c)) {
                window.remove(s.charAt(l));
                l++;
            }
            window.add(c);
            best = Math.max(best, r - l + 1);
        }
        return best;
    }
}

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = set()
        l = best = 0
        for r, c in enumerate(s):
            while c in window:
                window.remove(s[l])
                l += 1
            window.add(c)
            best = max(best, r - l + 1)
        return best

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> window;
        int l = 0, best = 0;
        for (int r = 0; r < (int)s.size(); r++) {
            char c = s[r];
            while (window.count(c)) {
                window.erase(s[l]);
                l++;
            }
            window.insert(c);
            best = max(best, r - l + 1);
        }
        return best;
    }
};

function lengthOfLongestSubstring(s) {
    const window = new Set();
    let l = 0, best = 0;
    for (let r = 0; r < s.length; r++) {
        const c = s[r];
        while (window.has(c)) {
            window.delete(s[l]);
            l++;
        }
        window.add(c);
        best = Math.max(best, r - l + 1);
    }
    return best;
}

3Optimal (sliding window with last-seen index)

TimeO(n)One pass, O(1) work per character.

SpaceO(k)A fixed table of 128 entries, one per ASCII character.

Instead of removing characters one by one, remember the last index where each character appeared. When s[r] was last seen at index p inside the window, the new window must start at p + 1, so jump l there directly. Use l = max(l, p + 1) so an old occurrence before the window never pulls l backwards.

Create last[128] filled with -1, set l = 0.
For each r: l = max(l, last[s[r]] + 1).
Set last[s[r]] = r and update best with r - l + 1.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] last = new int[128];
        Arrays.fill(last, -1);
        int l = 0, best = 0;
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            l = Math.max(l, last[c] + 1);
            last[c] = r;
            best = Math.max(best, r - l + 1);
        }
        return best;
    }
}

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}  # char -> last index
        l = best = 0
        for r, c in enumerate(s):
            l = max(l, last.get(c, -1) + 1)
            last[c] = r
            best = max(best, r - l + 1)
        return best

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> last(128, -1);
        int l = 0, best = 0;
        for (int r = 0; r < (int)s.size(); r++) {
            unsigned char c = s[r];
            l = max(l, last[c] + 1);
            last[c] = r;
            best = max(best, r - l + 1);
        }
        return best;
    }
};

function lengthOfLongestSubstring(s) {
    const last = new Array(128).fill(-1);
    let l = 0, best = 0;
    for (let r = 0; r < s.length; r++) {
        const c = s.charCodeAt(r);
        l = Math.max(l, last[c] + 1);
        last[c] = r;
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Edge cases to test

Empty string
All characters the same
All characters different: the answer is the whole length
A repeat far behind the current window, like "abba", must not move the window start backwards
Spaces and symbols count as characters too

Hints

Hint 1

A substring is a contiguous window. How would you check one window for repeats quickly?

Hint 2

If the window s[l..r] has no repeats and s[r + 1] is new, the window just grows. What should happen when s[r + 1] is already inside?

Hint 3

Remember the last index of each character. On a repeat, jump the left edge just past that index, but never move it left.

FAQ

What is the best time complexity for Longest Substring Without Repeating Characters?

Optimal (sliding window with last-seen index) runs in O(n) time and O(k) extra space. One pass, O(1) work per character.

Which pattern does Longest Substring Without Repeating Characters use?

It is a arrays & hashing problem that uses the sliding window · variable pattern. Other problems with the same pattern: Minimum Size Subarray Sum, Count of Subarrays with Product Less Than K, Longest Repeating Character Replacement.

Is there a brute force solution for Longest Substring Without Repeating Characters?

Yes. Brute force takes O(n²) time and O(k) space. Try every start index.

Which edge cases should I test for Longest Substring Without Repeating Characters?

Empty string; All characters the same; All characters different: the answer is the whole length; A repeat far behind the current window, like "abba", must not move the window start backwards; Spaces and symbols count as characters too.