Wednesday, February 11, 2015

LeetCode [3] Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0, n = s.size(), l = 0, r = 0;
        map<char, int> mp;
        while(r<n){
            while(mp[s[r]]>0){
                mp[s[l]]--;
                l++;
            }
            mp[s[r]]++;
            if(ret<r-l+1) ret = r-l+1;
            r++;
        }
        return ret;
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0, r = 0, n = s.length();
        int ret = 0;
        Set<Character> set = new HashSet<>();
        while(l<=r && r<n)
        {
            if(set.contains(s.charAt(r)))
            {
                set.remove(s.charAt(l++));
            }
            else
            {
                ret = Math.max(ret, r-l+1);
                set.add(s.charAt(r++));
            }
        }
        return ret;
    }
}
at

No comments:

Post a Comment