Java O(n) solution


  • 1
    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            if(s == null) {
                return 0;
            } else if (s.length() < 2) {
                return s.length();
            }
            int[] flags = new int[256];
            Arrays.fill(flags, -1);
            int start = 0;
            int end = 0;
            int max = 0;
            while (end < s.length()) {
                char curr = s.charAt(end);
                int lastIdx = flags[curr];
                if(lastIdx >= start) {
                    start = lastIdx + 1;
                }
                flags[curr] = end;
                end++;
                max = Math.max(max, end - start);
            }
            return max;
        }
    }
    

  • 1
    S

    Python equivalent

            if s == None:
                return 0
            elif len(s) < 2:
                return len(s)
    
            flags = [-1]*256
            start = 0
            end = 0
            max_ = 0
            while end < len(s):
                curr = s[end]
                lastIdx = flags[ord(curr)]
                if lastIdx >= start:
                    start = lastIdx + 1
    
                flags[ord(curr)] = end;
                end += 1
                max_ = max(max_, end - start)
            
            return max_
    

  • 0

    @slcott thanks for the Python implementation, and it's my honor to be the first to upvote you


Log in to reply
 

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