Longest Substring Without Repeating Characters
Problem Description
Given a string s, find the length of the longest substring without duplicate characters.
Example 1:
Explanation: The answer is "abc", with the length of 3.
Example 2:
Explanation: The answer is "b", with the length of 1.
Example 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
sconsists of English letters, digits, symbols and spaces.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The most straightforward way to solve this problem is by checking each possible substring to see if it contains all unique characters. We can iterate over all possible starting points and ending points for substrings and check for uniqueness.
Code:
- Time Complexity: O(n^3). There are two nested loops and checking whether a substring contains all unique characters is O(n).
- Space Complexity: O(min(n, m)), where n is the length of the string and m is the character set size (limited to 26 for this problem).
2. Sliding Window using HashSet
Intuition:
To reduce the complexity, we can use a sliding window technique. Instead of checking every substring, we can maintain a window and move it to the right while ensuring all characters within the window are unique.
Code:
- Time Complexity: O(2n) = O(n). In the worst case, each character will be visited twice.
- Space Complexity: O(min(n, m)). The set is used to store the unique characters in the window.
3. Sliding Window using HashMap
Intuition:
Further optimization can be done by optimizing the move of the start pointer. We can use a hash map to track the last seen index of each character, which allows skipping over sections of the string already known to contain non-unique characters.
Code:
- Time Complexity: O(n). Each character in the string is processed at most once.
- Space Complexity: O(min(n, m)). HashMap space is used to store last indices of characters.