Longest Substring Without Repeating Characters

1package pkg5leetcode;2 3/*4 * LeetCode 3: Longest Substring Without Repeating Characters  (Medium)5 * -------------------------------------------------------------------6 * Find the length of the longest substring without repeating characters.7 *8 * APPROACH: sliding window + last-seen index map. Move left past the last9 * duplicate when a repeat is found inside the window.10 * COMPLEXITY: Time O(n), Space O(min(n, charset)).11 */12import java.util.*;13 14public class leetcode7LongestSubstringNoRepeat {15 16    static int lengthOfLongestSubstring(String s) {17        Map<Character, Integer> last = new HashMap<>();18        int left = 0, best = 0;19        for (int right = 0; right < s.length(); right++) {20            char c = s.charAt(right);21            if (last.containsKey(c) && last.get(c) >= left) {22                left = last.get(c) + 1;        // shrink window past the duplicate23            }24            last.put(c, right);25            best = Math.max(best, right - left + 1);26        }27        return best;28    }29 30    public static void main(String[] args) {31        check(lengthOfLongestSubstring("abcabcbb") == 3, "abcabcbb");32        check(lengthOfLongestSubstring("bbbbb") == 1, "bbbbb");33        check(lengthOfLongestSubstring("pwwkew") == 3, "pwwkew");34        check(lengthOfLongestSubstring("") == 0, "empty");35        check(lengthOfLongestSubstring("dvdf") == 3, "dvdf");36        System.out.println("leetcode7LongestSubstringNoRepeat: all tests passed");37    }38 39    static void check(boolean cond, String name) {40        if (!cond) throw new AssertionError("FAILED: " + name);41        System.out.println("  PASS " + name);42    }43}