“Programmer essentials”

The sliding window method, also known as the ruler method (may not be equal, something like this =. =), can be used to solve some problems to find the properties (length, etc.) of continuous intervals that meet certain conditions. Because the interval is continuous, when the interval changes, the search space can be pruned by the old calculation results, which reduces the repeated calculation and time complexity. Problems such as “please find xx of the most x interval (substring, subarray) satisfying XX” can be solved using this method.

The longest string without repetition

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

Enter: s = “abcabcbb”

Output: 3

Explanation: Since the oldest string without repeating characters is “ABC”, its length is 3.

Before because I did a similar topic, my first idea is to use ASLL code, the characters into corresponding number, corresponding to an array of coordinates, using an array of storage to the occurrence of a string of number, but in the process of implementation, I found in the process of character turn into, is very trouble, so I thought of a data structure, hash table, We don’t have to worry about that with hash tables

We combine double Pointers, we iterate over the right pointer, we iterate over the element into the hash table, and when we encounter a repeating element in the hash table, we move the pointer, we move to the next bit of the repeating element, and the right pointer moves again.

public int lengthOfLongestSubstring(String s) { Set<Character> a=new HashSet<>(); int n=s.length(); int right=0,max=0; for (int i=0; i<n; i++){ if(i! =0){ a.remove(s.charAt(i-1)); } while (right < n && ! a.contains(s.charAt(right))){ a.add(s.charAt(right)); right++; } max=Math.max(max,right-i); } return max; }Copy the code

String arrangement

Given two strings s1 and s2, write a function to determine whether S2 contains a permutation of s1. In other words, one of the permutations of S1 is a substring of S2.

Requirements:

1 <= s1.length, s2.length <= 104

S1 and S2 contain only lowercase letters

Input: s1 = “ab” s2 = “eidbaooo”

Output: true,

Explanation: S2 contains one of the permutations of S1 (“ba”).

Input: s1= “ab” s2 = “eidboaoo”

Output: false

At the very beginning, this problem reminded me of the solution of my last problem, which used the coordinate of array to represent the element. Since its qualification condition only contains lowercase letters, we can use the value of ASLL to represent the element well.

There are too many kinds of substrings. But because of substrings, as long as we have the same kind of elements and the same number of elements, we can judge that they are the same, but in different order.

public boolean checkInclusion(String s1, String s2) { int [] num1=new int[26]; int [] num2=new int[26]; if((s2.length()-s1.length())<0){ return false; } for(int I =0; int I =0; i<s1.length(); i++){ num1[s1.charAt(i)-'a']++; num2[s2.charAt(i)-'a']++; } if(Arrays.equals(num1,num2)){ return true; } for(int I =s1.length(); i<s2.length(); I ++){// Add a new element num2[s2.charat (I)-'a']++; / / remove the first element in the window num2 [s2. The charAt (I - s1. The length () - 'a'] -; if(Arrays.equals(num1,num2)){ return true; } } return false; }Copy the code

Because we’re storing letters in an array, we just have to check if the elements in the array are the same and we know if the strings are the same.

I don’t know where I learned it, but I never forgot how to use it, so it’s pretty easy to use it myself.