无重复字符的最长子串

小鱼儿 2023-08-17 16:39 46阅读 0赞

[LeetCode 3][]  
[参考][Link 1]

#### 题目描述 ####

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

**示例 1:**

> 输入: “abcabcbb”  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

**示例 2:**

> 输入: “bbbbb”  
> 输出: 1  
> 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

**示例 3:**

> 输入: “pwwkew”  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。  
> 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

#### 题目解析 ####

暴力破解

public class Solution { 
        public int lengthOfLongestSubstring(String s) { 
            int n = s.length();
            int ans = 0;
            for (int i = 0; i < n; i++)
                for (int j = i + 1; j <= n; j++)
                    if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
            return ans;
        }
    
        public boolean allUnique(String s, int start, int end) { 
            Set<Character> set = new HashSet<>();
            for (int i = start; i < end; i++) { 
                Character ch = s.charAt(i);
                if (set.contains(ch)) return false;
                set.add(ch);
            }
            return true;
        }
    }

滑动窗口

import java.util.*;
    
    class Solution { 
        public int lengthOfLongestSubstring(String s) { 
            if(s.length() == 0)
                return 0;
    
            int res = 0;
            HashMap<Character, Integer> map = new HashMap();
            for(int left = 0, right = 0; right < s.length(); right++){ 
                char c = s.charAt(right);
                if(map.containsKey(c))
                    left = Math.max(left, map.get(c) + 1);
                map.put(c, right);
                res = Math.max(res, right - left + 1);
            }
            System.out.println(res);
            return res;
        }
    }

[LeetCode 3]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[Link 1]: https://www.nowcoder.com/discuss/196946?type=post&order=time&pos=&page=1