Leetcode 3. Longest Substring Without Repeating Characters

Question

Given a string, find the longest substring without repeated characters and return its length.

Solution - Brute Force

The most straightforward method. We use two loops to exhaust all substrings, and then use a function to determine whether there are duplicate characters in the substring.

Time complexity: two loops, plus the loop in the function that determines whether the substring satisfies the conditions, O(n³).

Space complexity: A set is used to determine whether there are duplicate characters in the substring. Since there are no repeated characters in the set, the longest possible one is the entire character set. Assuming the size of the character set is m, then the longest length of the set is m. On the other hand, if the length of the string is less than m, it is n. Then the longest set is n. In summary, the space complexity is O(min(m, n)).

Solution - Sliding Window

In the above solution, we assume that when i takes 0,

j is set to 1, to determine whether there are duplicate characters in the string str[0,1).

j is set to 2 to determine whether there are duplicate characters in the string str[0,2).

j is set to 3 to determine if there are any duplicate characters in the string str[0,3).

j is set to 4 to determine whether there are duplicate characters in the string str[0,4).

There are a lot of repetitive work, because if there are no repeated characters in str[0,3), we don’t need to determine whether there are repeated characters in the entire string str[0,4), but only need to determine whether str[3] is in str[0,3) or not.

If it’s not, it means that there are no duplicate characters in str[0,4).

If it is, then str[0,5), str[0,6), str[0,7) must have duplicate characters. So at this time, there is not need to continue loop with j, just i++ to enter the next loop.

We can see the process as the orange window moving to the right.

To determine whether a character is in the string, we can put the char in the map. The char is the key and it’s index is the value. So that we know the last occurance of a char in the string.

We can further optimize it. Let’s look at the example.

When the c pointed to by j exists in the preceding substring abcd, i is moved forward to b at this time, and the substring still contains c, and i must continue to move, so it can be optimized here. We can move i directly to the next position of c!

int result = 0;

Map<Character, Integer> tempMap = new HashMap<>();

for (int i = 0, j = 0; j < s.length(); j++) {
    // find repeat, skip i - j'
    if (tempMap.containsKey(s.charAt(j))) {
        i = Math.max(tempMap.get(s.charAt(j)), i);
    }

    result = Math.max(result, j - i + 1);
    // j + 1 means next time i will be move directly to here
    tempMap.put(s.charAt(j), j + 1);
}

return result;

Because i is jumping, the characters stored before map are not removed, so Math.max(map.get(s.charAt(j)), i) is used to make sure that the obtained index is not in front of i.

j is incremented by 1 for each loop, because the jump of i already guarantees that there are no duplicate in str[i, j].

Question

Similar Questions

Solution - Brute Force

Solution - Sliding Window