This is the 7th day of my participation in the August Text Challenge.More challenges in August

The title

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

Source: LeetCode link: leetcode-cn.com/problems/lo…

Example:

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

Implementation scheme 1: profiteering crack

Implementation steps:

  1. Define variablesmaxLengthRepresents the maximum length
  2. Use double Pointers to intercept strings that do not contain duplicates
  3. Compute the substring length, reserving the larger value tomaxLength
public int lengthOfLongestSubstring(String s) {
    int len = s.length();
    if (s == null || s.length() == 0) {
        return 0;
    }
    int maxLength = 1;
    for (int start = 0; start < len; start++) {
        for (int end = start + 1; end < len; end++) {
            String subStr = s.substring(start, end);
            if(subStr.indexOf(s.charAt(end)) ! = -1) {
                break;
            }
            int subLen = end - start + 1;
            if(subLen > maxLength) { maxLength = subLen; }}}return maxLength;
}
Copy the code

Implementation scheme 2: hash table + double pointer

Implementation logic:

  • Define hash tables that temporarily store substring characters and duplicate lookup
  • Iterates over the string, positioning the substring through a two-pointer loop
    • Determines whether the right pointer data exists in the hash table
      • No: Records to the hash table, moves to the right, and calculates the length
      • If yes, delete the element in the hash table and move the left pointer
    • Finally, check again to see if the right pointer element still exists
  • Calculate the substring length each time, comparing and reserving the maximum value
int hash(char key) {
    return key;
}

public int lengthOfLongestSubstring3(String s) {
    int len;
    // Length of the source string
    if (s == null || (len = s.length()) == 0) {
        return 0;
    }
    // The longest unrepeatable substring length
    int res = 0;
    // The left-most character index of the substring
    int left = 0;
    // The rightmost character index of the substring
    int right = 0;

    // 1. Define a hash table that supports all ASCII characters
    char[] chs = new char[128];
    // 2. Iterate over all characters of the string
    while (right < len) {
        char rightChar = s.charAt(right); // Right pointer character
        char c = chs[(chs.length - 1) & hash(rightChar)]; / / the hash algorithm
        if(rightChar ! = c) {// Not repeated
            // 2.1. Double pointer positioning substring index: right pointer increment
            right++;
            // Record non-repeating characters into the hash table
            chs[(chs.length - 1) & hash(rightChar)] = rightChar;
            // 3. Record the substring length each time and calculate the maximum value
            int size = right - left; // The length of each substring is not repeated
            res = res > size ? res : size;
        } else { // repeat
            // 2.2. Double-pointer positioned substring index: left pointer increment. Remove leftmost character from hash table: assign default value
            char leftChar = s.charAt(left++);
            chs[(chs.length - 1) & hash(leftChar)] = '\u0000'; }}return res;
}
Copy the code

Making the address

Case address

other

The majority of stubborn friends, if you read the article!! Please don’t be stingy with your comments!! If there is a better way to solve the problem or I solve the problem in the lack of place, the article writing is not good, I hope you can give me a comment or two!! Thank you all!!