首页 > 其他 > 详细

最长不含有重复字符的子字符串

时间:2019-01-12 11:52:21      阅读:45      评论:0      收藏:0      [点我收藏+]

标签:turn   定义   cin   const   距离   urn   串串   pty   扫描   

题目

  请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。假设字符串中只包含‘a’~‘z’的字符。例如,在字符串“arabcacfr”中,最长的不含重复字符的子字符串是“acfr”,长度为 4

思路

  定义函数f(i)表示以第i个字符结尾的不包含重复字符的子字符串的最长长度,从左到右扫描,计算第i个字符串结尾的不包含重复的字符的子字符串的最长长度时f(i)时,已经知道f(i-1);

  1.   如果第i个字符之前没有出现过,那么f(i)=f(i-1)+1;
  2.   若果第i个字符之前出现过,那么先计算第i个字符和他上次出现在字符串中的位置距离,记为d

      1>.如果d<=f(i-1),意味着在第i个字符出现两次所夹得字符串串中间没有其他字符,第i个字符出现在f(i-1)所对应的最长字符串中。即f(i)=d;

      2>.如果d>f(i-1),此时第i个字符出现在f(i-1)对应的最长子字符串之前,所以仍然有f(i)=f(f-1)+1;

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

class Solution
{
    public:
        int max_str_duplication(const string &s);
};
int Solution::max_str_duplication(const string &s)
{
    if(s.empty()||s.length()<=0)
        return -1;
        
    int max_len=0;
    int curr_len=0; 
    //每个字符上次出现在字符串位置中的下标,-1是没有出现过 
    vector<int> position(26,-1); 
    for(int i=0;i<s.length();++i)
    {
        int per_index=position[s[i]-a];
        if(per_index<0||i-per_index>curr_len)
            ++curr_len;
        else
        {
            max_len=max(max_len,curr_len);
            curr_len=i-per_index; 
        }
        position[s[i]-a]=i;
    }
    return max(max_len,curr_len);
}
int main()
{
    string str;
    cin>>str;
    Solution s;
    cout<<s.max_str_duplication(str)<<endl;
    return 0;
}

 

最长不含有重复字符的子字符串

标签:turn   定义   cin   const   距离   urn   串串   pty   扫描   

原文:https://www.cnblogs.com/tianzeng/p/10258973.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号