Make writing a habit together! This is the 11th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

The title

The oldest string without repeating characters

Given a string s, 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

Tip:

0 <= s.length <= 5 * 104 s The value consists of letters, digits, symbols, and SpacesCopy the code

Answer key

Analysis of the problem solving

Their thinking

  1. This problem is a typical “sliding time window” algorithm problem.

  2. We can read strings as fast or slow Pointers, with I representing the start position of the substring and Rk representing the current position of the substring.

We can use hash to determine not repeating substrings. If the string exists in the hash table, the next loop is entered. If it doesn’t exist, put it in the collection and move the right pointer again.

  1. And then finally, ans is used to store the maximum substring length, and then the comparison isrk - i + 1That’s right pointer – left pointer + 1

The complexity of time complexity O (N) space complexity O (| Σ |)

The problem solving code

The solution code is as follows (there are detailed notes in the code) :

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // Hash collection, which records whether each string has ever appeared
        Set<Character> occ = new HashSet<>();
        int n = s.length();
        // Right pointer, starting with -1, corresponds to the left side of our string boundary
        int rk = -1, ans = 0;
        for (int i = 0; i < n; i++) {
            if(i ! =0) {
                // Move the left pointer right to delete a character
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1< n && ! occ.contains(s.charAt(rk +1))) {
                // The pointer moves right
                occ.add(s.charAt(rk + 1));
                rk++;
            }

            A string from I to rk is the longest non-repeating substring
            ans = Math.max(ans, rk - i + 1);
        }
        returnans; }}Copy the code

Feedback results after submission (because the topic has not been optimized, the performance is mediocre) :

The reference information

  • 3. The largest string without repeating characters