LeetCode #3 Longest Substring Without Repeating Characters
Problem
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.Solution — Hash Map
Using a hash map to save all letters and modify current head once there is a repeating letter occurs.
Complexity
It takes O(n) time to iterate s, where n denotes to length of s. And it takes O(1)/O(logn) time to search and insert for hash map in average/worst cases. Thus, its time complexity will be O(n)/O(nlogn) in average/worst cases.
Because of the hash map, it uses O(n) extra space. Or you can say O(128) = O(1) because size of ASCII code is 128 which is the limit of all keys in hash map.
Solution — ASCII List
It’s with the same idea of previous approach but use a list instead of a hash map.
Complexity
It’s trivial that time complexity is O(n), where n denotes to length of s.
It’s clear that the size of list is 128 so its space complexity is O(128) = O(1).
