Given a string, find the length of the smallest string that does not contain repeating characters.
Leetcode-cn.com/problems/lo…
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 = “BBBBB” Output: 1 Explanation: Since the oldest string without repeating characters is “b”, its length is 1.
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.
Example 4:
Input: s = “output: 0
Tip:
0 <= s.length <= 5 * 10^4
S consists of letters, digits, symbols, and Spaces
Java algorithm
Ideas:
- First, we split the problem into string splitting permutations and combinations, and string checking itself,
- After trying to run it, the calculation timed out
- Optimization idea
- A non-repeating string is the longest. If it finds the same length, it stops and moves to a larger number of digits
- The official solution is nicer
package sj.shimmer.algorithm;
import java.util.HashSet;
import java.util.Set;
/** * Created by SJ on 2021/1/27. */
class D3 {
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("abcabcbb"));
System.out.println(lengthOfLongestSubstring("bbbbb"));
System.out.println(lengthOfLongestSubstring("pwwkew"));
System.out.println(lengthOfLongestSubstring(""));
}
public static int lengthOfLongestSubstring(String string) {
if (string==null||string.length()==0) {
return 0;
}
int length = 1;
return Math.max(length,getCombination(string, 2));
}
public static int getCombination(String string, int sLength) {
if (string==null||string.length()<sLength) {
return 0;
}
for (int i = 0; i < string.length(); i++) {
int sub = sLength + i;
if (sub >string.length()) {
break;
}
String substring = string.substring(i, sub);
if(! hasRepait(substring)) {returnMath.max(sLength,getCombination(string,++sLength)); }}return 0;
}
public static boolean hasRepait(String string){
Set<Character> set = new HashSet();
for (int i = 0; i < string.length(); i++) {
char c = string.charAt(i);
if (set.contains(c)) {
return true;
}
set.add(c);
}
return false; }}Copy the code
The official solution
The sliding window
To find a substring in a string is to slide the left and right boundaries of the substring through the string based on conditions, similar to sliding a window
The left and right Pointers traverse the list once, saving a lot of loops
-
Left boundary K, right boundary K, right boundary moves right continuously in each round, left boundary moves right when stopping or completing polling
-
The search starts at the KTH string, and each search adds a character to the hashset. If the move to j+1 is repeated, the longest character in position k, j is found, and the round can be stopped
-
The next round starts with k+1 and k+1 does not repeat, and k+1 does not repeat either, so simply remove the char from the set for k and move the right boundary with j
-
.
-
By comparing the maximum value recorded in each round, it can be obtained
Advantages: save a lot of repeated calculation, space-time optimization is very high, the left and right Pointers only go through once
Time complexity: O(N), where N is the length of the string. Left and right Pointers traverse the entire string once each.
Space complexity: O(σ ∣) where σ represents the character set (the characters that can appear in a string) and ∣ σ ∣ the size of the character set.
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>(); // hash set, used to judge weights
int length = s.length();
// The right pointer, starting with -1, means we are to the left of the string's left boundary and have not started moving
int rightIndex = -1, resultLength = 0;
for (int i = 0; i < length; ++i) {
if(i ! =0) {
set.remove(s.charAt(i - 1));// Move the left pointer one space to the right to remove a character; Avoid affecting subsequent replay checks
}
while (rightIndex + 1< length && ! set.contains(s.charAt(rightIndex +1))) {
// Keep moving the right pointer
set.add(s.charAt(rightIndex + 1));
++rightIndex;
}
// rightIndex -i + 1 is the longest length found in the current round (I is the left pointer)
resultLength = Math.max(resultLength, rightIndex - i + 1);
}
return resultLength;
}
Copy the code