LeetCode!! 3. Longest Substring Without Repeating Characters-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode!! 3. Longest Substring Without Repeating Characters。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

参考资料：左程云算法课

3. Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.

 

Example 1:

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

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

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.
 

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

思路：
首先，以str[i]为例，计算局部最优解 以str[i]为结尾的无重复字符的最长子串的长度。然后，遍历字符串，即i取0，1，…, n-1，取局部最优解的最大值，得到全局最优解。
具体地，求 以str[i]为结尾的无重复字符的最长子串的长度，可以使用动态规划的方法。
dp[i]表示 以str[i]为结尾的无重复字符的最长子串的长度。
以str[i]为结尾的无重复字符的子串不停地向左扩，直到扩不动了为止。扩不动的原因有两个：
第一，碰到了与str[i]相同的字符；
第二，碰到了dp[i-1]的局部最优解对应的开头的前一个位置，也就是令dp[i-1]扩不动的地方。
上面两个位置取最大，就是令以str[i]为结尾的无重复字符的子串向左扩不下去的地方。此时，可以求得dp[i]。

一些实现细节：
使用数组map记录，遍历到i字符时，之前的所有字符最近出现过的位置。
注意：“还没出现过”的位置不能使用默认值0，而是指定为-1.
这是因为，‘0’ 已经有自己的含义了，如map['a']=0表示字符’a’最近一次出现是在0位置。文章来源地址https://www.toymoban.com/news/detail-480345.html

// 写法1：有dp表的动态规划
 public int lengthOfLongestSubstring3(String s) 
    {
        if(s==null || s.length()==0){
            return 0;
        }

        char[] chs = s.toCharArray();
        int n=chs.length;
        int[] dp = new int[n];
        dp[0]=1;
        int[] map = new int[256];
        for(int i=0;i<256;i++){
            map[i]=-1;
        }
        map[chs[0]]=0;
        int res=1;
        for(int i=1;i<n;i++){
            dp[i] = i-Math.max(map[chs[i]],i-1-dp[i-1]);// Math.max(map[chs[i]],i-1-dp[i-1])是 局部最优开头的前一位的坐标
            if(dp[i]>res){res=dp[i];}
            map[chs[i]]=i;
          
        }
        return res;

    }

// 写法2：省去了dp表，只使用有限几个变量，因为dp[i]在dp表中只依赖dp[i-1]
     public int lengthOfLongestSubstring(String s) 
    {
        if(s==null || s.length()==0){
            return 0;
        }
        char[] str = s.toCharArray();
        int n = str.length;
        int[] map = new int[256];
        for(int i=0;i<n;i++){
            map[str[i]]=-1;
        }
        int pre = -1;
        int cur=1;
        int res=1;
        map[str[0]]=0;
        for(int i=1;i<n;i++){
            pre = Math.max(pre,map[str[i]]);
            cur = i-pre;
            res = cur>res?cur:res;
            map[str[i]]=i;
        }
        return res;
    }

// 写法2： 和上面一样的写法，这里有些注释，可供参考
    public int lengthOfLongestSubstring2(String s) 
    {
        if(s==null || s.length()==0)
        {
            return 0;
        }
        char[] str = s.toCharArray();
        int[] map=new int[256];// <char,position>
        for(int i=0;i<256;i++)
        {
            map[i]=-1; 
            // 因为‘0’已经有含义了，它表示 the first index
            // 所以我们选择另外一种数字表示 “还没出现过”
        }
        // LSs who ends up with [i], 
        //  pre ： dp[i-1]'s previous index of its locally optimal start
        int pre = -1;
        int cur = 0;// local opt
        int ans=cur;// global opt
        for(int i=0;i<str.length;i++)
        {
            pre = Math.max(pre,map[str[i]]);
            cur = i-pre;
            map[str[i]]=i;
            ans = Math.max(ans,cur);
        }
      return ans;
    }