Thursday, May 24, 2018

[2018-Interview] Longest Substring Without Repeating Characters

Original question: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

My answer:



class Solution {
    public int lengthOfLongestSubstring(String s) {
        int globalMaxLength = 1;
        int localMaxLength = 1;
        Map<Character, Integer> charIndex = new HashMap<Character, Integer>();
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() < 2) {
            return 1;
        }
        int l = 0;
        int r = 0;
        while (r < s.length()) {
            if (charIndex.containsKey(s.charAt(r)) && l <= charIndex.get(s.charAt(r))) {
                // l <= charIndex.get(s.charAt(r)), 
                // the opposite of l > charIndex.get(s.charAt(r)), 
                // which is good way to ignore the repeating char existed before
                globalMaxLength = Math.max(r - l, globalMaxLength);
                l = charIndex.get(s.charAt(r)) + 1;
            }
            charIndex.put(s.charAt(r), r);
            r ++;
        }
        globalMaxLength = Math.max(r - l, globalMaxLength);
        return globalMaxLength;
    }
}

No comments:

Post a Comment