AlgoPressAppearance
48-最长不含重复字符的子字符串
题目描述
https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
s.length <= 40000
注意：本题与主站 3 题相同：https://leetcode.cn/problems/longest-substring-without-repeating-characters/
思路1 动态规划
实现代码
csharp
public class Solution {
// 基本思路： 试试动态规划
public int LengthOfLongestSubstring(string s) {
if (s.Length <= 1)
{
return s.Length;
}
int maxLength = 1;
int left = 0;
int right = left + 1;
while (right < s.Length)
{
int index = left;
// look same char from left
while (index < right)
{
if (s[index] == s[right])
{
left = index + 1;
}
index++;
}
int currentLength = right - left + 1;
maxLength = currentLength > maxLength ? currentLength : maxLength;
right++;
}
return maxLength;
}
}
第二次写, 注意 start 边界处理 start = i + 1
csharp
public class Solution {
//子字符串，应该是连续的，使用双指针(也叫滑动窗口)
public int LengthOfLongestSubstring(string s) {
if(s.Length < 2){
return s.Length;
}
int start=0;
int end=1;
int count = 1;
while(end<s.Length){
for(int i=start; i<end; i++){
if(s[i] == s[end]){
start = i+1;
}
}
count = Math.Max(count, end - start + 1);
end++;
}
return count;
}
}
第三次写，使用Hash表记录位置 注意求取左边界 start 的时候，不能直接判断其所在字符串+1，而要看 start 是否已经在其后面 比如 abba 当求到最后一个 a 的说 dict['a'] +1 = 1 , 但实际上 start 已经是2了，在求b的时候设置过
csharp
public class Solution {
//子字符串，应该是连续的，使用双指针(也叫滑动窗口)
public int LengthOfLongestSubstring(string s) {
if(s.Length < 2){
return s.Length;
}
int start=0;
int end=1;
int count = 1;
Dictionary<char,int> dict = new Dictionary<char,int>();
dict.Add(s[0],0);
for(int j = 1; j < s.Length; j++){
if(dict.ContainsKey(s[j])){
start = Math.Max(dict[s[j]]+1,start);
dict[s[j]] = j;
}
else{
dict.Add(s[j],j);
}
count = Math.Max(count, j - start + 1);
}
return count;
}
}
思路：动态规划
定义 dp[i] 表示以 i 结尾的最长子字符串的长度 再用另一个Hash表记录 s[i] 字符最后出现的位置，那么 当 s[i] 字符没有出现的时候 dp[i] = dp[i-1] + 1 说明前面都没有重复 如果出现过，且该位置小于 dp[i-1]的长度，那么 dp[i] = i - 所在 + 1; 中途统计最大值 maxCount;
csharp
public class Solution {
public int LengthOfLongestSubstring(string s) {
//边界处理
if(s.Length <=1 ){
return s.Length;
}
int[] dp = new int[s.Length];
dp[0] = 1; //初始化，第一个肯定不重复
Dictionary<char,int> dict = new Dictionary<char,int>();
dict.Add(s[0],0);
int maxCount = 1;
for(int i=1; i<s.Length; i++){
if(dict.ContainsKey(s[i])){
//如果这个字符出现过，看他出现在前面其他重复字符串长度之前，还是之后
//取其小的值作为结果
int index = dict[s[i]];
dp[i] = Math.Min(dp[i-1]+1, i-index);
dict[s[i]] = i; //更新字典索引
}
else{
dp[i] = dp[i-1]+1;
dict.Add(s[i],i);
}
maxCount = Math.Max(maxCount,dp[i]);
}
return maxCount;
}
}
复习动规：20220508
csharp
public class Solution {
public int LengthOfLongestSubstring(string s) {
if(s == null || s.Length == 0){
return 0;
}
//定义动态规划数组 dp[i] 表示已 i 结尾的数字的最大不重复字符串的长度
int[] dp = new int[s.Length];
dp[0] = 1;
//创建字典保存字符出现的地方
Dictionary<char,int> dict = new Dictionary<char,int>();
dict.Add(s[0],0);
int maxLen = 1;
for(int i=1; i<s.Length; i++){
if(!dict.ContainsKey(s[i])){ //没重复
dp[i] = dp[i-1] + 1; //累加长度
dict.Add(s[i],i); //加入索引
}
else{ //有重复
int index = dict[s[i]]; //找出索引位置
int len = i - index ; //计算长度
dp[i] = Math.Min(dp[i-1]+1,len); //要查看前面是否有出现过更小的长度，两者取小
dict[s[i]] = i; //更新索引
}
maxLen = Math.Max(dp[i],maxLen);
}
return maxLen;
}
}
复习：滑动窗口 2022-05-11
其实不需要使用dp记录结果，我们只需要记录正确 left 位置，和当前位置计算得到 len 即可。
csharp
public class Solution {
public int LengthOfLongestSubstring(string s) {
//思路 Hash 表储存位置，一旦重复，就清空重来
Dictionary<char,int> dict = new Dictionary<char,int>();
int left = 0;
int max = 0;
for(int i=0; i<s.Length; i++){
if(!dict.ContainsKey(s[i])){ //不重复
dict.Add(s[i],i);
}
else{ //重复
//dict.Clear(); //此处不能删除前面所有字符，而是要删掉出现这个字符的位置 : 如测试用例 dvdf
left = Math.Max(dict[s[i]]+1,left); //取到重复位置的下一个，这里要注意如果重复位置比left还靠左，要取当前的left，如 xmmabcxf 当第二次遇到 x 的时候，不能把 left 设置为0,因为 m重复的时候，已经设置过left了，要以大的为准
Console.WriteLine("left={0}",left);
dict[s[i]] = i;
}
max = Math.Max(max,i-left+1);
}
return max;
}
}