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: HashTable + Sliding Window
Using a hashtable to remember the last index of every char. And keep tracking the starting point of a valid substring.
start = max(start, last[s[i]] + 1)
ans = max(ans, i – start + 1)
Time complexity: O(n)
Space complexity: O(128)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int lengthOfLongestSubstring(string s) { const int n = s.length(); int ans = 0; vector<int> idx(128, -1); for (int i = 0, j = 0; j < n; ++j) { i = max(i,idx[s[j]] + 1); ans = max(ans, j - i + 1); idx[s[j]] = j; } return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public int lengthOfLongestSubstring(String s) { int[] last = new int[128]; Arrays.fill(last, -1); int start = 0; int ans = 0; for (int i = 0; i < s.length(); ++i) { if (last[s.charAt(i)] != -1) start = Math.max(start, last[s.charAt(i)] + 1); last[s.charAt(i)] = i; ans = Math.max(ans, i - start + 1); } return ans; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 |
# Author: Huahua class Solution: def lengthOfLongestSubstring(self, s): last = [-1] * 128 ans = 0 start = 0 for i, ch in enumerate(s): if last[ord(ch)] != -1: start = max(start, last[ord(ch)] + 1) ans = max(ans, i - start + 1) last[ord(ch)] = i return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment