This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

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

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3.Copy the code

Example 2:

Input: s = "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1.Copy the code

Example 3:

Input: s = "pwwkew" Output: 3 Explanation: Since the oldest string without repeating characters is "wKE", its length is 3. Note that your answer must be the length of the substring, "pwke" is a subsequence, not a substring.Copy the code

Example 4:

Input: s = "output: 0Copy the code

Tip:

• 0 <= s.length <= 5 * 104
• S consists of letters, digits, symbols, and Spaces

2. Algorithm analysis

Let’s start with an example of how we can get through this problem in optimal time complexity.

Using the string abcabcbb in example 1, find the longest string that does not contain repeating characters, starting with each character. For the string in example 1, we list these results, with parentheses indicating the selected character and the longest string:

The longest string beginning with (a)bcabcbb is (ABC)abcbb; The longest string starting with a(b)cabcbb is a(bca) BCBB; The longest string starting with ab(c)abcbb is ab(CAB) CBB. The longest string starting with ABC (a) BCBB is ABC (ABC)bb; The longest string starting with abca(b) CBB is abca(BC)bb. The longest string starting with abcab(c)bb is abcab(cb)b. The longest string starting with abcabc(b)b is abcabc(b)b; The longest string starting with abcabcb(b) is abcabcb(b).

What was found? If we incrementally enumerate the start of the substring, then the end of the substring is also incrementally!

At each step, we move the left pointer one space to the right to indicate that we begin enumerating the next character as the starting position, and then we can keep moving the right pointer to the right, making sure that there are no duplicate characters in the substring corresponding to the two Pointers. At the end of the move, the substring corresponds to the oldest string that does not contain repeating characters, starting with the left pointer. We record the length of this substring;

At the end of the enumeration, the length of the longest substring we find is the answer.

3. Code implementation

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // hash set to record whether each character has ever appeared
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // The right pointer, starting with -1, means we are to the left of the string's left boundary and have not started moving
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if(i ! =0) {
                // The left pointer moves one space to the right to remove a character
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1< n && ! occ.contains(s.charAt(rk +1))) {
                // Keep moving the right pointer
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // The i-rk character is an extremely long non-repeating character substring
            ans = Math.max(ans, rk - i + 1);
        }
        returnans; }}Copy the code