Lunski's Clutter

This is a place to put my clutters, no matter you like it or not, welcome here.

0%

3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

1
2
3
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
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.

Example 4:

1
2
Input: s = ""
Output: 0

最長不重複子字串,沒看過的加入set, 跟最長size比較更新最大值,看過就從set刪除。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Time: O(n), Space: O(1)
class Solution {
public int lengthOfLongestSubstring(String s) {

int i = 0, j = 0, max = 0;
// Upcasting allowed to access only parent class members and child class specified members
Set<Character> set = new HashSet<>();

while (j < s.length()) { // O(1)
if (!set.contains(s.charAt(j))) { // O(1), O(1)
set.add(s.charAt(j++)); // O(1) ++ to next
max = Math.max(max, set.size());
} else {
set.remove(s.charAt(i++)); // O(1)
}
}
return max;
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Time: O(n), Space: O(1)

class Solution:
def lengthOfLongestSubstrig(self, s:str) -> int:
characters = set()
left=right=ans=0
length=len(s)

while right < length:
print(characters, right, left, ans)
if s[right] in characters:
characters.remove(s[left])
left+=1
else:
characters.add(s[right])
right+=1
ans = max(ans,right-left)
return ans
print(Solution().lengthOfLongestSubstrig('abcabcbb'))

如果你覺得這篇文章很棒,請你不吝點讚 (゚∀゚)

Welcome to my other publishing channels