Solution


Approach 1: Brute Force

Intuition

Check all the substring one by one to see if it has no duplicate character.

Algorithm

Suppose we have a function boolean allUnique(String substring) which will return true if the characters in the substring are all unique, otherwise false. We can iterate through all the possible substrings of the given string s and call the function allUnique. If it turns out to be true, then we update our answer of the maximum length of substring without duplicate characters.

Now let's fill the missing parts:

  1. To enumerate all substrings of a given string, we enumerate the start and end indices of them. Suppose the start and end indices are and , respectively. Then we have (here end index is exclusive by convention). Thus, using two nested loops with from 0 to and from to , we can enumerate all the substrings of s.

  2. To check if one string has duplicate characters, we can use a set. We iterate through all the characters in the string and put them into the set one by one. Before putting one character, we check if the set already contains it. If so, we return false. After the loop, we return true.

Complexity Analysis

  • Time complexity : .

    To verify if characters within index range are all unique, we need to scan all of them. Thus, it costs time.

    For a given i, the sum of time costed by each is

    Thus, the sum of all the time consumption is:

  • Space complexity : . We need space for checking a substring has no duplicate characters, where is the size of the Set. The size of the Set is upper bounded by the size of the string and the size of the charset/alphabet .


Approach 2: Sliding Window

Algorithm

The naive approach is very straightforward. But it is too slow. So how can we optimize it?

In the naive approaches, we repeatedly check a substring to see if it has duplicate character. But it is unnecessary. If a substring from index to is already checked to have no duplicate characters. We only need to check if is already in the substring .

To check if a character is already in the substring, we can scan the substring, which leads to an algorithm. But we can do better.

By using HashSet as a sliding window, checking if a character in the current can be done in .

A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in the array/string which usually defined by the start and end indices, i.e. (left-closed, right-open). A sliding window is a window "slides" its two boundaries to the certain direction. For example, if we slide to the right by element, then it becomes (left-closed, right-open).

Back to our problem. We use HashSet to store the characters in current window ( initially). Then we slide the index to the right. If it is not in the HashSet, we slide further. Doing so until s[j] is already in the HashSet. At this point, we found the maximum size of substrings without duplicate characters start with index . If we do this for all , we get our answer.

Complexity Analysis

  • Time complexity : . In the worst case each character will be visited twice by and .

  • Space complexity : . Same as the previous approach. We need space for the sliding window, where is the size of the Set. The size of the Set is upper bounded by the size of the string and the size of the charset/alphabet .


Approach 3: Sliding Window Optimized

The above solution requires at most 2n steps. In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.

The reason is that if have a duplicate in the range with index , we don't need to increase little by little. We can skip all the elements in the range and let to be directly.

Java (Using HashMap)

Java (Assuming ASCII 128)

The previous implements all have no assumption on the charset of the string s.

If we know that the charset is rather small, we can replace the Map with an integer array as direct access table.

Commonly used tables are:

  • int[26] for Letters 'a' - 'z' or 'A' - 'Z'
  • int[128] for ASCII
  • int[256] for Extended ASCII

Complexity Analysis

  • Time complexity : . Index will iterate times.

  • Space complexity (HashMap) : . Same as the previous approach.

  • Space complexity (Table): . is the size of the charset.