“This article has participated in the call for good writing activities, click to view: the back end, the big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!”
The title is as follows:
Given a string s, find the length of the smallest string that does not contain repeating characters.
Find the longest string in a given string that does not contain repeated characters. We can use violent exhaustive method to get all the substrings in the string, and then judge the length of non-repeated substrings. Finally return the longest string length, for example:
For such a string, we first iterate over it from the beginning, fetching a:
Select the next character b and check whether it is repeated. If it is not repeated, continue to insert it into a new string:
So does the next character c:
The new string has a length of 3, and we continue iterating from the second character of the string:
Looking at the next character c, we still put in the new string:
Until the character B is encountered, the repeat occurs:
The length of the current new string is still recorded and iterated from the third character of the original string:
And so on, we get a table of the length of a substring without repeating characters:
At this point, you only need to fetch the maximum value in the length table, that is, the maximum string length without repeating characters in the string.
Once you know the idea of the algorithm, you can write code:
public static int lengthOfLongestSubstring(String s) {
// Use the List collection to determine if a character is repeated
List<Character> list = new ArrayList<>();
// Store the length of all non-repeating substrings
List<Integer> lenList = new ArrayList<>();
// Record the substring length
int count = 0;
char[] charArray = s.toCharArray();
// enumerate all substrings
for (int i = 0; i < charArray.length; ++i) {
for (int j = i; j < charArray.length; ++j) {
// Check if the character is repeated
if (list.contains(charArray[j])) {
// If present, record the length of the current substring
lenList.add(count);
// Set empty, count returns to 0
list.clear();
count = 0;
// End the loop
break;
} else {
// If not, add itlist.add(charArray[j]); count++; }}}// Sort the set of non-repeating substring lengths from largest to smallest
lenList.sort((o1, o2) -> o2 - o1);
// The first element sorted is the maximum value in the set
return lenList.get(0);
}
Copy the codeError while submitting code:
We don’t have to consider what all don’t input the original case, without input, directly return to zero length, the length of 1 input, we also must be considered separately, because of just procedure only when duplicate characters will record the length of the substring, and if the input string of length 1, there will be no repeat of the, So handle both cases separately and modify the code:
public static int lengthOfLongestSubstring(String s) {
// If the string length is 1, 1 is returned
if (s.length() == 1) {
return 1;
}
// If no input is entered, 0 is returned
if (s.length() == 0) {
return 0;
}
// Use the List collection to determine if a character is repeated
List<Character> list = new ArrayList<>();
// Store the length of all non-repeating substrings
List<Integer> lenList = new ArrayList<>();
// Record the substring length
int count = 0;
char[] charArray = s.toCharArray();
for (int i = 0; i < charArray.length; ++i) {
for (int j = i; j < charArray.length; ++j) {
// Check if the character is repeated
if (list.contains(charArray[j])) {
// If present, record the length of the current substring
lenList.add(count);
// Set empty, count returns to 0
list.clear();
count = 0;
// End the loop
break;
} else {
// If not, add itlist.add(charArray[j]); count++; }}}// Sort the set of non-repeating substring lengths from largest to smallest
lenList.sort((o1, o2) -> o2 - o1);
// The first element sorted is the maximum value in the set
return lenList.get(0);
}
Copy the codePass the test:
Brute force solve the problem, but the execution efficiency is very low, so here is another solution: sliding window.
For a string like this:
We set up a sliding window in which the substring is the oldest string without repeating characters, define two Pointers to divide the window’s left and right boundaries, and specify the length of the oldest string at this time to be 1:
Move the right pointer to the right to expand the range of the sliding window. At this time, the maximum string length is 2:
Continuing to move the right pointer, the maximum length of the string is 3:
When you move the right pointer again, the character A appears in the sliding window:
At this point, we need to shrink the sliding window so that it does not repeat the current character A and move the left pointer right:
When the sliding window is no longer repeated with character A, expand the sliding window and move right to the right, at this time, the maximum string length is still 3:
At this time, the character B is found to be the same as the character in the window, and continue to narrow the sliding window:
After no repetition, expand the sliding window and move the right pointer to the right:
And so on until the end of the traversal.
The code is as follows:
public static int lengthOfLongestSubstring(String s) {
// If no input is entered, 0 is returned
if (s.length() == 0) {
return 0;
}
// Define the left edge of the sliding window
int left = 0;
// Define the right edge of the sliding window
int right = 0;
// The maximum length of a substring without repetition
int maxLen = 1;
// Simulate a sliding window
Set<Character> set = new HashSet<>();
// Iterate over the string
while(right < s.length()){
// If the characters in the sliding window are the same as the current characters, zoom out the sliding window until there is no duplication
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
// Calculate the current sliding window length and compare with maxLen, taking the maximum as the new non-repeating substring length
maxLen = Math.max(maxLen, right - left + 1);
// Expand the sliding window
set.add(s.charAt(right));
right++;
}
return maxLen;
}
Copy the codePass the test:
There are still areas where the algorithm can be improved, such as:
For such a string, when the sliding window encounters repeated characters:
At this time, zoom out the sliding window, left to move right until the character w is deleted:
Is there a way to move left to the next character of the repeating character? We can use a HashMap to simulate a sliding window, because a HashMap can store a value, we can just let it store the index of a character. So when we encounter a duplicate character w, we simply pull index 3 of w from the HashMap, and let the left pointer jump to the next index 4.
The code is as follows:
public static int lengthOfLongestSubstring(String s) {
// If no input is entered, 0 is returned
if (s.length() == 0) {
return 0;
}
// Define the left edge of the sliding window
int left = 0;
// Define the right edge of the sliding window
int right = 0;
// The maximum length of a substring without repetition
int maxLen = 1;
// Simulate a sliding window
Map<Character, Integer> map = new HashMap<>();
// Iterate over the string
while (right < s.length()) {
// If the character in the sliding window is the same as the current character, the sliding window is shrunk
int index = map.getOrDefault(s.charAt(right), -1);
// Jump the left pointer directly to the next character of the repeating character in the sliding window
left = Math.max(left, index + 1);
// Calculate the current sliding window length and compare with maxLen, taking the maximum as the new non-repeating substring length
maxLen = Math.max(maxLen, right - left + 1);
// Expand the sliding window
map.put(s.charAt(right), right);
right++;
}
return maxLen;
}
Copy the code