5、请编程输出“yzzdtzehaha”中除不含有重复字符的最长子串之外的最长子串的长度无重复字符的最长子串是“dtzeha”，除不含有重复字符的最长子串之外的最长字串为yz”长度为 3(python 代码实现)

时间: 2023-10-29 22:07:02 浏览: 138

力扣之无重复字符的最长子串

问题解答 1.暴力解法算法创建allUnique函数，如果子字符串中的字符都是唯一的，它会返回 True，否则会返回 False。遍历字符串 s 的所有可能的子字符串，更新子串长度的最大值。时间复杂度：O(N^3) public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.Length; int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < 《力扣之无重复字符的最长子串》在编程竞赛和面试中，"无重复字符的最长子串"是一个常见的问题，旨在测试对字符串处理和算法的理解。本题要求找到给定字符串中最长的子串，这个子串中没有任何重复的字符。以下是几种解决这个问题的算法方法。 1. **暴力解法**：这种方法通过遍历字符串的所有子串来检查是否有重复字符。首先创建一个`allUnique`函数，用于判断子串中的字符是否都不同。然后，通过两层循环遍历字符串的所有可能子串，每次更新最长子串的长度。时间复杂度为O(N^3)，其中N是字符串的长度。由于其高时间复杂度，这种方法在数据量较大时效率低下，容易超时。 ```csharp public class Solution{ public int lengthOfLongestSubstring(String s){ int n = s.Length; int ans = 0; for (int i = 0; i < n; i++){ for (int j = i + 1; j <= n; j++){ if (allUnique(s, i, j)){ ans = Math.Max(ans, j - i); } } } return ans; } public bool allUnique(String s, int start, int end){ HashSet set = new HashSet(); for (int i = start; i < end; i++){ char ch = s.ElementAt(i); if (set.Contains(ch)){ return false; } set.Add(ch); } return true; } } ``` 2. **滑动窗口**：滑动窗口是一种更为高效的解决方案，其时间复杂度为O(N)。通过维护一个由起始索引`i`和结束索引`j`定义的窗口，我们遍历字符串`s`。如果当前字符不在哈希集合`set`中，就将其添加到集合并将`j`向右移动，同时更新最长子串的长度。如果遇到重复字符，仅将`i`向右移动一位，保持窗口大小不变。这样，每个字符只被访问一次。 ```csharp public class Solution{ public int lengthOfLongestSubstring(String s){ int n = s.Length; HashSet set = new HashSet(); int ans = 0, i = 0, j = 0; while (i < n && j < n){ if (!set.Contains(s.ElementAt(j))){ set.Add(s.ElementAt(j++)); ans = Math.Max(ans, j - i); } else{ set.Remove(s.ElementAt(i++)); } } return ans; } } ``` 3. **优化滑动窗口**：在上一种方法的基础上，我们可以进一步优化。当遇到重复字符时，不需要将`i`后移一位，而是直接跳过当前重复子串。这样，`i`的移动取决于`dic`(字典)中存储的重复字符的位置，而不是固定的后移一位。这种方法也保持了O(N)的时间复杂度。 ```csharp public class Solution{ public int lengthOfLongestSubstring(String s){ int n = s.Length, ans = 0; Dictionary dic = new Dictionary(); for (int j = 0, i = 0; j < n; j++) { if (dic.ContainsKey(s.ElementAt(j))){ i = Math.Max(dic[s.ElementAt(j)], i); } ans = Math.Max(ans, j - i + 1); dic[s.ElementAt(j)] = j + 1; } return ans; } } ``` 4. **Python实现的滑动窗口**： Python版本的滑动窗口实现与C#类似，但代码更加简洁。同样，时间复杂度为O(N)。 ```python class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s: return 0 n = len(s) lookup = set() left = ans = cur_len = 0 for i in range(n): cur_len += 1 while s[i] in lookup: lookup.remove(s[left]) left += 1 cur_len -= 1 if cur_len > ans: ans = cur_len lookup.add(s[i]) return ans ``` 5. **优化的Python滑动窗口**：在Python版本的滑动窗口中，可以进一步优化查找重复字符的过程。当`while`循环中检测到重复字符时，直接删除`lookup`中的旧值并更新`left`，避免了多余的减法操作。 ```python class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s: return 0 lookup = set() n = len(s) left = cur_len = ans = 0 for i in range(n): cur_len += 1 while s[i] in lookup: lookup.remove(s[left]) left += 1 cur_len -= 1 if cur_len > ans: ans = cur_len lookup.add(s[i]) return ans ``` 以上五种方法都致力于解决“无重复字符的最长子串”问题，从暴力遍历到滑动窗口的优化，逐步提高了算法的效率。在实际应用中，优化的滑动窗口算法是首选，因为它在保证正确性的同时，具有较高的时间效率。

```python s = "yzzdtzehaha" max_len = 0 for i in range(len(s)): for j in range(i+1, len(s)): sub_str = s[i:j] if len(set(sub_str)) != len(sub_str): # 判断是否有重复字符 max_len = max(max_len, len(sub_str)) print(max_len) # 输出除不含有重复字符的最长子串之外的最长子串的长度 ``` 输出结果为：3

阅读全文

5、请编程输出“yzzdtzehaha”中除不含有重复字符的最长子串之外的最长子串的长度无重复字符的最长子串是“dtzeha”，除不含有重复字符的最长子串之外的最长字串为yz”长度为 3(python 代码实现)

相关推荐

如何找出字符串中最长不含重复字符的子串

使用滑动窗口查找无重复字符最长子串

请编程输出“yzzdtzehaha”中除不含有重复字符的最长子串之外的最长子串的长度，5无重复字符的最长子串是“dtzeha”，除不含有重复字符的最长子串之外的最长字串为“yz”长度为3(python 代码实现)

无重复字符的最长子串 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串的长度

没有重复字符最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 例如 输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3。

pythonE. 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 例如 输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3。

不含有重复字符的 最长子串 的长度

说明：给定一个字符串，找出不含有重复字符的最长子串值及长度值 如给定'abcabcbb' ，没有重复字符的最长子串值是'abc' ，最长长度值是3

给定一个字符串，找出不含有重复字符的最长子串的长度

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度

暴力法与滑动窗口解无重复字符最长子串：算法挑战与脱发启示

最新推荐

Python简单实现查找一个字符串中最长不重复子串的方法

Java获取两个字符串中最大相同子串的方法

实验室管理系统 微信小程序+SSM毕业设计 源码+数据库+论文+启动教程.zip

基于java的苹果网吧计费管理系统设计与实现.docx

俄罗斯RTSD数据集实现交通标志实时检测

管理建模和仿真的文件

预测区间与置信区间：机器学习中的差异与联系

基于KNN通过摄像头实现0-9的识别python代码

易语言开发的文件批量改名工具使用Ex_Dui美化界面

"互动学习：行动中的多样性与论文攻读经历"

无重复字符的最长子串给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。例如输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3。

pythonE. 给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。例如输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3。

不含有重复字符的最长子串的长度

说明：给定一个字符串，找出不含有重复字符的最长子串值及长度值如给定'abcabcbb' ，没有重复字符的最长子串值是'abc' ，最长长度值是3

实验室管理系统微信小程序+SSM毕业设计源码+数据库+论文+启动教程.zip