leetcode 3. Longest Substring Without Repeating Characters 最长不重复子串和重复子串

r囧r小猫 2022-06-09 06:15 160阅读 0赞

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

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

题意就不说了，这道题是求的是最大的**不重复**的子串，求解重复子串可以类似采用**[最长公共子串][Link 1]** 的解法。  
**最长重复子串**在这里指的是在只一个字符串中找到最长的重复子串，这个和最长公共子串很像，其实DP的解法思想是一样的，但是处理问题对象不一样，  
**最长公共子串**求的是字符串a和b的公共子串，最长重复子串求得是字符串a的最长的重复的子串  
dp\[i\]\[j\]表示0到i和0到j的两个字符串的最长公共解。  
这道题最大的启发就是对最长不重复子串的理解（不能包含任何重复的元素），其实遍历求解即可完成。

import java.util.HashSet;
    import java.util.Set;
    
    
    public class Solution 
    {
        /*
         * 这个想法很不错，为什么这么想呢？
         * 
         * 因为我们是要求得最长不重复字符串，那么目标字符串的每一个元素都unique的
         * 也就是没有任何的重复的子元素，那么我们开始遍历，然后逐步移动end指针
         *     当不包含当前的元素的时候，set添加元素，end++
         *     当包含当前元素的时候，表示出现了重复，set清空，beg++，end=beg，这样开始重复遍历
         * 
         * */
         public int lengthOfLongestSubstring(String s) 
         {
             //特殊情况
             if(s==null || s.length()<=0)
                 return 0;
    
             int maxLen=0;
             int beg=0,end=0;
             Set<Character> set=new HashSet<>();
             while(end<s.length())
             {
                 if(set.contains(s.charAt(end)))
                 {
                     set.clear();
                     beg++;
                     end=beg;
                 }else 
                 {
                     set.add(s.charAt(end));
                     end++;
                     if(end-beg>maxLen)
                         maxLen=end-beg;
                 }
             }
    
             return maxLen;
    
         }
    
         /*
          * 既然有最大不重复子串，那么就存在最长重复子串，可以参考如下链接
          * http://www.cnblogs.com/xiaodeyao/p/5332834.html
          * 
          * 最长重复子串在这里指的是在只一个字符串中找到最长的重复子串，这个和最长公共子串很像，
          * 其实DP的解法思想是一样的，但是处理问题对象不一样，
          * 最长公共子串求的是字符串a和b的公共子串，最长重复子串求得是字符串a的最长的重复的子串
          * dp[i][j]表示0到i和0到j的两个字符串的最长公共解。
          * 
          * 不过这个和最长公共子串还是略有不同的。
          * 
          * */
         public int lengthOfLongestRepetSubstring(String s) 
         {
             if(s==null || s.length()<=0)
                 return 0;
    
             int [][]dp=new int[s.length()+1][s.length()+1];
             dp[0][0]=1;
             for(int i=1;i<=s.length();i++)
             {
                 for(int j=1;j<s.length();j++)
                 {
                     if(s.charAt(i-1)==s.charAt(j-1))
                         dp[i][j]=dp[i-1][j-1]+1;
                     else
                         dp[i][j]=0;
                 }
             }
    
             /*
              * 
              * 最长重复子串求得是字符串a的最长的重复的子串，这个是要排除自身，
              * 所以要避免dp矩阵的对角线的计算
              * 
              * */
             int maxLen=0;
             for(int i=1;i<=s.length();i++)
             {
                 for(int j=1;j<s.length();j++)
                 {
                     if(i!=j && dp[i][j]>maxLen)
                         maxLen=dp[i][j];
                 }
             }
    
             return maxLen;
         }
    
        public static void main(String[] args) 
        {
            Solution solution=new Solution();
            String one="aaAaaAsfr";
    
            int d=solution.lengthOfLongestRepetSubstring(one);
            System.out.println(d);
        }
    
    
    }

下面是C++代码做法

#include <iostream>
    #include <string>
    #include <set>
    using namespace std;
    
    class Solution 
    {
    public:
        int lengthOfLongestSubstring(string s) 
        {
            if (s.length() <= 1)
                return s.length();
    
            int maxLen = 0;
            set<char> myset;
            int beg = 0, end = 0;
            while (end < s.length())
            {
                if (myset.find(s[end])!=myset.end())
                {
                    myset.clear();
                    beg++;
                    end = beg;
                }
                else
                {
                    myset.insert(s[end]);
                    end++;
                    maxLen = (end - beg)>maxLen ? (end - beg) : maxLen;
                }
            }
            return maxLen;
        }
    };

[Link 1]: http://blog.csdn.net/hackbuteer1/article/details/6686931