My accepted Java solution in O(N)


  • 0
    P
    public int lengthOfLongestSubstring(String s) {
            int len = s.length();
            if (len == 0) return 0;
            int maxLen = 0;
            int curLen = 0; int curStart = 0;
            Map<Character, Integer> map = new HashMap<Character, Integer>();
            for (int i =0; i < len; i++) {
                Integer offset = map.get(s.charAt(i));
                if (offset == null)
                  curLen++;
                else if (offset >= curStart) {
                    curLen = i - offset;
                    curStart = offset + 1;
                } else {
                    curLen++;
                }
                map.put(s.charAt(i), i);
                if (curLen > maxLen) {
                    maxLen = curLen;
                }
            }
            return maxLen;
        }

  • 2
    L

    I have a same idea with you. But less code:

    public class Solution
    {
        public int lengthOfLongestSubstring(String s)
        {
            // Last position of character in the string.
            final Map<Character, Integer> pos = new HashMap<>();
            // Start point of current sub string.
            int start = 0;
            // Length of current longest sub string.
            int max = 0;
            
            for (int i = 0; i < s.length(); ++i)
            {
                final char character = s.charAt(i);
                // When meet a character, to check whether we need to adjust the starting position.
                // if we didn't meet same character before, the starting position won't change, 
                // otherwise, we check last position of this character, 
                // if it's after the current starting point, we move the starting position after it.
                start = Math.max(start, (pos.containsKey(character) ? (pos.get(character) + 1) : 0));
                max = Math.max(max, i - start + 1);
                pos.put(character, i);
            }
            
            return max;
        }
    }

Log in to reply
 

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