3. Longest Substring Without Repeating Characters
Longest Substring Without Repeating Characters (LeetCode 3) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
- Blind 75 · #13 of 75 · Sliding Window
- NeetCode 150 · #16 of 150 · Sliding Window
- NeetCode 250 · #38 of 250 · Sliding Window
How to solve Longest Substring Without Repeating Characters
Longest Substring Without Repeating Characters is a Variable Size Sliding Window problem, part of Sliding Window. Master variable-size sliding window for condition-based problems like longest substring without repeating characters.
Work towards the solution in these steps:
- Generate all possible substrings & check for each substring if it's valid and keep updating maxLen accordingly.
The reference solution runs in O(n) time and O(1) space.
The Longest Substring Without Repeating Characters solution and editorial walks through the full approach with reference code.
Problem statement
Given a string s, find the length of the longest substring without duplicate characters.
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:
- 0 <= s.length <= 5 104
- s consists of English letters, digits, symbols and spaces.
Topics and companies
Topics: Hash Table, String, Sliding Window.
Reported in interviews at Amazon, Bloomberg, Microsoft, Facebook, Apple, Adobe, eBay, Goldman Sachs, Google, Alation, VMware, Oracle and others.
How to practise Longest Substring Without Repeating Characters on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Longest Substring Without Repeating Characters in the code editor, or read the Longest Substring Without Repeating Characters editorial for a worked solution with its approach and complexity analysis.
Where Longest Substring Without Repeating Characters sits in the DSA pattern sheet
Problems related to Longest Substring Without Repeating Characters
Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:
- Contains Duplicate II — Easy, same subpattern
- Continuous Subarrays — Medium, same subpattern
- Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
- Frequency of the Most Frequent Element — Medium, same subpattern
- Fruit Into Baskets — Medium, same subpattern
- Jump Game VII — Medium, same subpattern
Longest Substring Without Repeating Characters FAQ
What is the LeetCode number of Longest Substring Without Repeating Characters?
Longest Substring Without Repeating Characters is LeetCode problem 3, rated Medium.
What pattern is used to solve Longest Substring Without Repeating Characters?
Longest Substring Without Repeating Characters is a Variable Size Sliding Window problem. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
What is the time complexity of Longest Substring Without Repeating Characters?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Longest Substring Without Repeating Characters?
Longest Substring Without Repeating Characters has been reported in interviews at Amazon, Bloomberg, Microsoft, Facebook, Apple, Adobe, eBay, Goldman Sachs, Google, Alation, VMware, Oracle and others.