LeetCode - 3. Longest Substring Without Repeating Characters3. Longest Substring Without Repeating Characters Problem's Link

 ----------------------------------------------------------------------------

Mean: 

找出一個字元串的最長無重複子串.

analyse:

使用map<char,int>來映射字元和下标的關系，然後維護一個下标值：下标最大的一個循環字元的前一個字元的下标.

然後分情況不斷更新answer即可.

Time complexity: O(N)

view code

#include<bits/stdc++.h>

using namespace std;

class Solution

{

public:

   int lengthOfLongestSubstring(string s)

   {

       int ans=0;

       int len=s.length();

       int currentLength=0;

       int recentCycleIndex=0;

       map<char,int> mp;

       for(int i=0; i<len; ++i)

       {

           if(mp.find(s[i])==mp.end())

               currentLength++;

           else

           {

               if(mp[s[i]]<=recentCycleIndex)

                   currentLength=i-recentCycleIndex;

               else

                   currentLength=i-mp[s[i]];

               recentCycleIndex=max(recentCycleIndex,mp[s[i]]);

           }

           mp[s[i]]=i;

           ans=max(ans,currentLength);

       }

       return ans;

   }

};

int main()

   string s;

   while(cin>>s)

       Solution solution;

       int answer=solution.lengthOfLongestSubstring(s);

       cout<<"============answer============="<<endl;

       cout<<answer<<endl;

   return 0;

}