Problem Statement
Find the length of the longest substring without repeating characters.
Example Inputs
- Input:
"abcabcbb"
- Output:
3 (substring: "abc")
- Input:
"bbbbb"
- Output:
1 (substring: "b")
- Input:
"pwwkew"
- Output:
3 (substring: "wke")
- Input:
"dvdf"
- Output:
3 (substring: "vdf")
JavaScript Method - Using Only String Methods
Approach
To find the longest substring without repeating characters, we can use a sliding window approach with two pointers and check each substring’s uniqueness by adjusting the start pointer when duplicates are found.
Steps
- Initialize an empty substring
uniqueSubstr, and variables maxLength = 0 and start = 0.
- Loop through each character using an index
end.
- For each character, check if it exists in
uniqueSubstr.
- If a character is repeated, increment
start until there are no duplicates in uniqueSubstr.
- Update
maxLength with the length of the current substring if it’s the largest so far.
- Continue until the end of the string.
Time & Space Complexity
- Time Complexity: O(n^2), because we repeatedly check for duplicates in the substring, which can take O(n).
- Space Complexity: O(n), as we store substrings.
Code Snippet
Dry Run
Example input: "abcabcbb"
- Loop start with
start = 0, uniqueSubstr = ""
a → uniqueSubstr = "a"b → uniqueSubstr = "ab"c → uniqueSubstr = "abc" (no duplicates so far)a → duplicate found, break- Update
maxLength = 3
- Final output:
3
Alternative Approach - Using Hash Map (Efficient)
Approach
We can use a hash map to store the last seen index of each character. This allows us to efficiently move the start pointer to skip over duplicates, reducing redundant checks.
Steps
- Initialize
start = 0, maxLength = 0, and an empty hash map charIndexMap.
- Loop through each character in the string with an index
end.
- If the character is already in
charIndexMap and is within the current substring, update start to charIndexMap[char] + 1 to skip over duplicates.
- Update
charIndexMap with the current index of the character.
- Update
maxLength with end - start + 1.
- Continue to the end of the string and return
maxLength.
Time & Space Complexity
- Time Complexity: O(n), as each character is processed only once.
- Space Complexity: O(n), due to the hash map storing character indices.
Code Snippet
Dry Run
Example input: "abcabcbb"
- Initialize:
start = 0, maxLength = 0, charIndexMap = {}
- Loop through characters:
a at index 0 → charIndexMap = { a: 0 }, maxLength = 1b at index 1 → charIndexMap = { a: 0, b: 1 }, maxLength = 2c at index 2 → charIndexMap = { a: 0, b: 1, c: 2 }, maxLength = 3a at index 3 (duplicate) → update start = 1- Final
maxLength = 3
Final output: 3
Complexity Analysis
JavaScript Method (Using String Methods)
- Time Complexity: O(n^2)
- Space Complexity: O(n)
Alternative Approach (Using Hash Map)
- Time Complexity: O(n)
- Space Complexity: O(n)
Conclusion
Finding the longest substring without repeating characters can be achieved through substring checks or using an efficient hash map approach. The hash map approach provides an optimal linear-time solution by keeping track of character indices.