1. The subject

Given a string, find the length of the smallest string that does not contain repeating characters.

Example 1: Input: “abcabcbb” Output: 3 Explanation: Since the oldest string without repeating characters is: “ABC”, its length is 3

Example 2: Input: “BBBBB” Output: 1 Explanation: Since the oldest string without repeating characters is: “b”, its length is 1

Example 3: Input: “pwwkew” Output: 3 Explanation: Since the oldest string without repeating characters is: “wke” or “Kew”, its length is 3 note: it must be the length of a substring. Substrings are contiguous characters and cannot jump characters in between. For example, “pwke” is a subseries, not a substring.

2

2.1 Idea 1: Sliding Windows

A window is typically a collection of elements defined by a start and end index in an array/string, that is [I, j) (left closed, right open), while a sliding window is a window that can “slide” two boundaries in one direction or another.

Such as: We slide [I, j] one element to the right, and it becomes [I +1, j+1) (left closed, right open). We use HashSet to store the characters currently in window [I, j)(originally j = I). Then we slide right index j, and if it’s not in HashSet, we keep sliding j, Until s[j] already exists in the HashSet, the oldest string that does not repeat itself will start with index I

Use a HashSet to store the characters currently in the sliding window. The initial HashSet is empty. The left I of the window does not move, and the right J slides right to traverse characters: j is the index pointing to the character. HashSet — [p] maxSubLength = 1 maxSubLength = 2

When j = 2, traversal character w, then the HashSet already contains the repeated character W, then the left I of the window slides to the right, the right j does not move, HashSet deletes the character pointed to by index I in turn until the HashSet no longer contains the character W, and then re-adds the traversal character W to the HashSet. Launch window J continue right – swipe.

The left I of the window does not move, and the right J continues to slide right to traverse the characters in turn: MaxSubLength = 3 maxSubLength = 3 maxSubLength = 3 maxSubLength = 3

When j = 5, traversal character w, and the HashSet already contains the repeated character W, then the left I of the window slides to the right, while the right j does not move, and the HashSet deletes the character pointed to by index I in turn until the HashSet no longer contains the character W, and then re-adds traversal character W to the HashSet, and starts the window J to slide right. If maxSubLength = 3

Code implementation:

public static int lengthOfLongestSubstring(String s) {
    if (s == null || "".equals(s)) {
        return 0;
    }
    int n = s.length();
    Set<Character> set = new HashSet<>();
    int maxLength = 0;
    int i = 0;
    int j = 0;
    while (i < n && j < n) {
        if(! set.contains(s.charAt(j))) { set.add(s.charAt(j++)); maxLength = Math.max(j - i, maxLength); }else{ set.remove(s.charAt(i++)); }}return maxLength;
}
Copy the code

2.2 Idea 2: Optimized sliding window

For the above sliding window method, instead of using collections to determine the existence of a character, you define a character-to-index map. When repeated characters are found, the window can be skipped immediately.

If there are characters in [I, j] that duplicate s[j], index j’, i.e. [I,… j’,… j), we don’t need to increment I, we can skip all elements in [I, j’] and change I to j’ + 1

For example: s = “pwwkew”, when j = 2, the window [0, 2) has the same character w as s[2], index is 1(j’ = 1), we can directly skip all elements within [0, 1], change I to 2(j’ + 1).

Code implementation:

public static int lengthOfLongestSubstring(String s) {
  if (s == null || "".equals(s)) {
		return 0;
	}
	int n = s.length();
	Map<Character, Integer> map = new HashMap<>(16);
	int maxLength = 0;
	for (int i = 0,j = 0; j < n; j++) {
		if (map.containsKey(s.charAt(j))) {
			i = Math.max(map.get(s.charAt(j)), i);
		}
		maxLength = Math.max(maxLength, j - i + 1);
		map.put(s.charAt(j), j + 1);
	}
	return maxLength;
}
Copy the code

2.3 Idea 3: Use a List to store unique characters

Each character in string S is iterated sequentially. If it is not a duplicate character, it is added to a list. If it is a duplicate character, it is deleted from the list and all the preceding characters, and then it is added to the list.

In the traversal process, the maximum number of characters stored in list is calculated, that is, the length of the longest string without repeated characters in string S.

Code implementation

public static int lengthOfLongestSubstring(String s) {
	if (s == null || "".equals(s)) {
		return 0;
	}
	List<Character> list = new ArrayList<>();
	int n = s.length();
	int maxLength = 0;
	for (int i = 0; i < n; i++) {
		int index = list.indexOf(s.charAt(i));
		if (index == -1) {
			list.add(s.charAt(i));
			maxLength = Math.max(list.size(), maxLength);
		} else {
			for (int j = index; j >= 0; j--) { list.remove(j); } list.add(s.charAt(i)); }}return maxLength;
}
Copy the code