This is a place to put my clutters, no matter you like it or not, welcome here.
0%
3. Longest Substring Without Repeating Characters
Posted onEdited onIn面試Views: Symbols count in article: 1.6kReading time ≈1 mins.
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; } }
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'))