This is the seventh day of my participation in the August More text Challenge. For details, see:August is more challenging

The oldest string with no duplicate characters

The title

Given a string s, find the longest 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. Example 2: Input: s = "pwwkew" Output: 3 Explanation: Since the oldest string without duplicate 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

Answer key

This question examines some uses of strings (string interception, search). During traversal, compare the current character to the previous non-repeating substring:

• The current character is in the substring, and the left edge of the substring is contracted to the next repeated bit value;
• If not repeated, the right boundary continues to expand.

For the maximum, compare the maximum length of the substring that appears.

Example:

s = “abcabcbb”

When starting, the left and right boundaries of the substring should point to the starting position. The currently intercepted substring STR should be null.The substring STR does not contain the current character A, so extend the right edge of the substring and continue to walk down.

When we loop to the second A, the situation is as follows:

In this case, the truncated substring contains the current character. Search for the repeated position in the substring and narrow the left boundary to the next bit of the repeated position. Continue the loop, take the maximum.

When the repetition occurs again:Still narrow the left edge. In this case, P1 is not simply moved to the next bit in the substring repeat position. The current substring repeat position is 0, and the next bit is 1. But if you move to 1, the left edge doesn’t shrink. So when you move, you have to add the original position of the left edge. P1 moves to position 2. In the same way, we take the maximum length of the substring in each iteration. When the last traversal is complete, return the maximum value.

code

var lengthOfLongestSubstring = function (s) {
    let p1 = 0, index = 0, max = 0
    while (index <= s.length) {
        let str = s.slice(p1, index)
        let isExitIndex = str.indexOf(s[index])
        if (isExitIndex > -1) p1 += isExitIndex + 1
        max = Math.max(max, str.length)
        index++
    }
    return max
};
Copy the code

Permutation of strings

The title

Given two strings s1 and s2, write a function to determine whether s2 contains the permutation of s1 ****.

In other words, one of the permutations of S1 is a substring of S2.

Example 1: Input: s1 = "ab" s2 = "eidBaooo" Output: true Explanation: S2 contains one of the permutations of S1 ("ba").Copy the code

Answer key

This question mainly examines whether the substring permutation can be associated with the use of character array solution. To be honest, AT first I didn’t think…

Use two arrays of length 26 to record the number of occurrences of each character in each string. Use an array of length 26 to record the number of occurrences in S1. As we traverse S2, we intercept possible substrings of S2 by using two left and right Pointers. Record the number of substring characters intercepted in an array of length 26. This is true when the array of S1 is equal to the array of truncated substrings.

code

var checkInclusion = function (s1, s2) {
    let arr1 = new Array(26).fill(0)
    let arr2 = new Array(26).fill(0)
    for (let i = 0; i < s1.length; i++) {
        arr1[s1[i].charCodeAt() - 'a'.charCodeAt()]++
    }
    let i = 0, j = 0
    while (i < s2.length) {
        arr2[s2[i].charCodeAt() - 'a'.charCodeAt()]++
        while (j <= i && arr2[s2[j].charCodeAt() - 'a'.charCodeAt()] > arr1[s2[j].charCodeAt() - 'a'.charCodeAt()]) {
            arr2[s2[j].charCodeAt() - 'a'.charCodeAt()]--
            j++
        }
        i++
        if (arr1.join(' ') === arr2.join(' ')) return true
    }
    return false
};
Copy the code

Topic source: Leetcode