daniel.baird
10/8/2018 - 3:55 AM

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

public int lengthOfLongestSubstring(String s) {
        // Keeps the index of the last place where the character was seen.
        HashMap<Character, Integer> seenCharacters = new HashMap<>();
        int longestRun = 0;
        int lastDuplicateBreak = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (seenCharacters.containsKey(c)) {
                int duplicateSeen = seenCharacters.get(c);
                if (duplicateSeen > lastDuplicateBreak) {
                    lastDuplicateBreak = duplicateSeen;
                }
            }

            seenCharacters.put(c, i);

            int currentRun = i - lastDuplicateBreak;
            if (currentRun > longestRun) {
                longestRun = currentRun;
            }
        }

        return longestRun;
    }