LeetCode刷题【剑指 Offer 48】最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• s.length <= 40000

注意：本题与主站 3 题相同：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

一般解法，一步步分析实现

一顿分析

以字符串abcabcbb为例

1. a的时候，最长为1，这个没啥问题 此时为1
2. ab的时候，前面有了a为1，而b又不在前面的a中，所以可以由前面的长度加1得到 此时为2
3. abc的时候，和前面的情况一样，新增的字符c在前面的范围中不存在则继续加1长度 此时长度为3
4. abca的时候，新增了个a，在前面不重复的长度为3的字符abc中找到了一个相同的，他的下标为0，那么只能从这个下标往后和新增的a组成最长不重复子串了，下标相差求得 此时长度为3
5. abcab的时候，比前面又多了个b，再次在前面的一个最长子串中尝试寻找b，发现存在，得到其下标为1，照样当前下标和查找到的下标求得新的最长子串长度为3
6. abcabc的时候，又多了个c，依旧重复上面的 此时长度为3
7. abcabcb，比前面多了个b，前面一个的最长子串为abc，查找得到了有重复的b，下标为4，和当前下标5求得新的最长子串长度为2
8. abcabcbb，再次和前面的最长子串cb比较查找，最终得到当前最长子串长度为1
9. 最终所有的情况中最长的为3

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0){
            return 0;
        }
        char[] arr = s.toCharArray();
        int[] dp = new int[s.length()];
        dp[0] = 1;
        int idx = 0;
        int max = 1;
        while (++idx < s.length()){
            int existIdx = existIdx(arr,idx - dp[idx-1]-1,idx-1,arr[idx]);
            if (existIdx==-1){
                dp[idx] = dp[idx-1]+1;
            }else{
                dp[idx] = idx-existIdx;
            }
            max = Math.max(max,dp[idx]);
        }
        return max;
    }

    public int existIdx(char[] arr , int left , int right , char c){
        while (++left <= right){
            if (arr[left] == c){
                return left;
            }
        }
        return -1;
    }
}

至于查找位置用的existIdx方法，这里的不同单个字符的数量比较有限，直接遍历查找即可。不是太大的性能问题