3 Longest Substring Without Repeating Characters *****

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

Examples:

Given"abcabcbb", the answer is"abc", which the length is 3.

Given"bbbbb", the answer is"b", with the length of 1.

Given"pwwkew", the answer is"wke", with the length of 3. Note that the answer must be asubstring,"pwke"is asubsequenceand not a substring.

• [x] Very important and hard to think about

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if ( s == null || s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        int j = 0;
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {

                j =Math.max(j, map.get(s.charAt(i)) + 1) ;
            }
            map.put(s.charAt(i), i);
            res = Math.max(res, i - j + 1);
        }
        return res;
    }
}

Approach #3 Sliding Window Optimized [Accepted]

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 ifs[j]s[j]have a duplicate in the range[i, j)[i,j)with indexj'j​′​​, we don't need to increaseiilittle by little. We can skip all the elements in the range[i, j'][i,j​′​​]and letiito bej' + 1j​′​​+1directly.

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

If we know that the charset is rather small, we can replace theMapwith 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

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}

Time complexity :O(n)O(n). Indexjjwill iteratenntimes.

Space complexity (HashMap) :O(min(m, n))O(min(m,n)). Same as the previous approach.

Space complexity (Table):O(m)O(m).mmis the size of the charset.