My 11 lines solution in O(n) time and O(1) space


  • 7
    W
    int lengthOfLongestSubstring(char* s) {
        int mp[256];
        for(int i = 0;i < 256;++i) mp[i] = -1;
        int len = strlen(s), first = 0, size = 0;
        for(int i = 0;i < len;++i){
            if(mp[s[i]] >= first)
                first = mp[s[i]] + 1;
            mp[s[i]] = i;
            if(size < i - first + 1)
                size = i - first + 1;
        }
        return size;
    }

  • 2
    U
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int start=0,i,max=0;
            int visited[256];
            memset(visited,-1,sizeof(visited));
            for(i=0;i<s.size();i++)
            {
                if(visited[s[i]]>=start)
                {
                    max = (i-start)>max ? (i-start):max;
    				start = visited[s[i]] + 1;
                }             
                visited[s[i]] = i;
            }
            return max>(i-start) ? max:(i-start);
        }
    };

  • 3
    S
    import java.util.*;
    public class Solution {
        public int lengthOfLongestSubstring(String s) {//abba
          	int first=0, size=0, len=s.length(); //len=4
          	Map<Character,Integer> mp=new HashMap<>(); //V is the last apper of K
          	for(int i=0;i<len;i++){ //i=0,1,2,3
          		Character c=(Character)s.charAt(i);
          		if(mp.containsKey(c)&&mp.get(c)>=first) first=mp.get(c)+1; 
          		mp.put(c,i);
          		if(size<(i-first+1)) size=i-first+1;
          	}
        return size;
        }
    }

  • 0
    W

    Could you explain the variant "first"?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.