LeetCode-3-无重复字符的最长子串
3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
提示：
0 <= s.length <= 5 * 104-
s由英文字母、数字、符号和空格组成
通过次数945,734
提交次数2,560,351
子串，子序列解法
首先第一想到的通用解法就是，以i结尾的子串 最长子串 的长度，然后求所有可能的结尾。然后在所有的可能答案中，找出最长！
在以i结尾的子串 最长子串 的长度 中求最大，就是本题的解，这也是经典的解法，对于求求子串和子序列问题。
现在就是用代码把这个解法能够完美实现的问题了。
假设我们现在有一个dp[] 数组存了以i-1结尾中最长子串的开始位置了，此时我们求 i 位置的最长子串
第一个因素：是我当前位置的字符上次出现的位置。
第二个因素：i-1位置结尾，可以往左推了多远。
为什么？
因为index=16往左推的时候，到index=12就结束了，所以index=11的字符，一定在index=12到index=16之间出现过。所以，index=17往左推的时候，一定越不过index=12这根线。
因素1和因素2谁离index=17近，就是以index为结尾所求的最长的子串。
public class Problem_0003_LongestSubstringWithoutRepeatingCharacters {
public static int lengthOfLongestSubstring(String str) {
if (str == null || str.equals("")) {//合法性判断
return 0;
}
char[] chas = str.toCharArray();//通用性写法，字符串转数据，和性能无关
int[] map = new int[256];//map数组 用来记录字符最后一次出现在字符串的index 循环中一起更新 map[chas[i]] = i;
for (int i = 0; i < 256; i++) {
map[i] = -1;//初始值-1
}
int resultLen = 0; //最后返回的result最长子串的长度
int pre = -1;
int cur = 0;//点前以i为结尾子串和(i-1)结尾最长子串
for (int i = 0; i != chas.length; i++) {
pre = Math.max(pre, map[chas[i]]);
cur = i - pre;
resultLen = Math.max(resultLen, cur);
map[chas[i]] = i;//更新当前子串最后出现的位置
}
return resultLen;
}
}
其他Top解法
Basic logic is, I have kept an array of size 128 for all ASCII characters, using the ASCII value of each character as an index of array I am saving the position of the character in this array. Using two pointers one to traverse all characters(end index of substring | right pointer) and other to find the repeating character(start index for substring | left pointer). I have filled the array with -1 so that index 0 can be used too. If the character is found in the array update the second pointer with the next index of that character, so we now know where to start the new substring. Check maxCount exverytime and find the length of substring by subtracting the difference of two pointers and adding 1.
public int lengthOfLongestSubstring(String s) {
if(s.length()==0) return 0;
int[] ascii = new int[128];
Arrays.fill(ascii,-1);
int maxCount = 0;
for(int i = 0, j = 0; i < s.length(); ++i){
if(ascii[s.charAt(i)] >= 0){
j = Math.max(j,ascii[s.charAt(i)]+1);
}
ascii[s.charAt(i)] = i;
maxCount = Math.max(maxCount, i-j+1);
}
return maxCount;
}
Thoughts Before Coding
- We can implement a sliding window approach
- We can keep track of our current left 'i' and right 'j' boundaries
of our current window
- For each of the new character 'c'
- If 'c' is already inside our current window
- We can shrink our window to remove 'c' before
adding 'c' to our window
- We will want to pick the window with the longest length
- We will need a quick way to determine if the current character
is inside our window
- We can create a HashSet to keep track of the current characters
inside our window
- Then for each of the character 'c'
- We can check if 'c' is inside the HashSet
Answer
- Create a HashSet 'seen' to keep track of the characters in our window
- Create a variable 'i' to be our left boundary, initially 0
- Create a variable 'max' to keep track of the longest window
- Iterate through the indices from '0 -> s.length() - 1', denoted as 'j'
- retrieve the character 'c' at index 'j'
- While 'seen' contains 'c'
- Remove the character 'd' that is located at index 'i' from 'seen'
- Increment 'i'
- Add 'c' to 'seen'
- Update 'max' if 'j - i + 1'
- Return 'max'
What is the Time and Space Complexity?
- Time Complexity = O(n), where 'n' is the length of the input string
- O(n), sliding window, visit each element at most twice
- Space Complexity = O(k), where 'k' is the number of unique characters
- O(k), 'seen' set
public class LongestSubstringWithoutRepeatingCharacters {
public int lengthOfLongestSubstring(String s) {
Set<Character> seen = new HashSet<>();
int i = 0, max = 0;
for (int j = 0; j < s.length(); j++) {
char c = s.charAt(j);
while (seen.contains(c)) {
seen.remove(s.charAt(i++));
}
seen.add(c);
max = Math.max(max, j - i + 1);
}
return max;
}
}
