Alg.17 Longest Substring Without Duplication

From algoexpert.io

In this problem, we need to write a function to find out the longest substring without any duplicate characters.

We iterate the original string and use a map to record the characters and their corresponding positions. Array “longest” stores the index of the current longest substring, “startIdx” is the current start point of a potential longest substring. When we get to a character, we determine whether we have met it before and if it appears after the current head, we can update the current “startIdx” according to this rule. Then we can update the “longest” by comparing the lengths of current potential longest substring and “longest”. Here is the code implementation:

public static String longestSubstringWithoutDuplication(String str) {
        int[] longest = {0, 1};
        int startIdx = 0;
        
        // Use a map to record the characters and its corresponding position
        Map<Character, Integer> table = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            // If the character we have Encountered before
            if (table.containsKey(str.charAt(i))) {
                // If this character appears after the current head,
                // we update the head
                if (table.get(str.charAt(i)) + 1 >= startIdx) {
                    startIdx = table.get(str.charAt(i)) + 1;
                }
            }
            table.put(str.charAt(i), i);
            
            // Update the current longest substring
            if (i - startIdx + 1 > longest[1] - longest[0]) {
                longest[0] = startIdx;
                longest[1] = i + 1;
            }
        }
    return str.substring(longest[0], longest[1]);
  }

Time complexity: O(n); Space complexity:O(n)

Donate