Thursday, April 10, 2014

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Solution: 
 Straight forward thinking. Use map to store the unique chars. If not in the map store it, cnt ++, if in the map, then store the len, next substring start from the previous same chars position
Notes:
1. store map value to a local , then change map value
2. consider the case when the longest substring is at the end: add sth after if in while loop

Code;
int lengthOfLongestSubstring(string s) {
   map bowl; // store position
   if(s.size()==0) return 0;
   int cnt=1;
   int st=0;
   bowl.insert(pair(s[0],0));

   int i=1;
   int len=cnt;
   while(i
   {
       if(bowl.find(s[i])==bowl.end())
       {
           bowl.insert(pair(s[i],i));
           cnt++;
       }
       else
       {
           if (len
           int sst = bowl[ s[i]]+1;
           int sss = bowl[ s[i] ];
           for (int tt =st; tt<= sss; tt++)
             bowl.erase(s[tt]);

            bowl.insert(pair(s[i],i));
            cnt=bowl.size();
            st = sst;
       }
       i++;
       if (i==S.size() && cnt > len)
        len = cnt;
   }
   return len;

}

No comments:

Post a Comment