无重复字符的最长子串 使用php来实现算法
时间: 2023-01-29 10:49:30 浏览: 86
无重复字符的最长子串是指在一个字符串中找到一个子串,该子串中的所有字符都是唯一的,并且该子串的长度最大。
下面是用 PHP 实现该算法的一种方法:
```
function longestSubstringWithoutRepeatingCharacters($s) {
$len = strlen($s);
$maxLen = 0;
$start = 0;
$seen = array();
for ($i = 0; $i < $len; $i++) {
$char = $s[$i];
if (isset($seen[$char])) {
$start = max($start, $seen[$char] + 1);
}
$seen[$char] = $i;
$maxLen = max($maxLen, $i - $start + 1);
}
return $maxLen;
}
```
上面的代码中,我们使用了一个变量 $seen$ 来记录每个字符最后一次出现的位置。然后,我们使用变量 $start$ 来记录当前子串的起始位置,并在每次遇到重复的字符时,将 $start$ 设为该字符上一次出现的位置加 1。这样,就可以保证当前子串中不会出现重复的字符。最后,我们使用变量 $maxLen$ 来记录最长子串的长度,并在每次更新 $start$ 和 $seen$ 后更新 $maxLen$。
使用上面的代码,你就可以在 PHP 中轻松求出无重复字符的最长子串了。
相关问题
如何生成无重复字符最长子串,生成代码
以下是一个示例生成无重复字符最长子串的代码:
```
def length_of_longest_substring(s: str) -> int:
# 初始化一个哈希表,用于记录字符最后一次出现的位置
char_dict = {}
# 初始化最长无重复字符子串的起始位置和长度
start = 0
max_len = 0
# 遍历字符串
for i in range(len(s)):
# 如果当前字符已经出现过,更新起始位置为上一次出现位置的下一个位置
if s[i] in char_dict and char_dict[s[i]] >= start:
start = char_dict[s[i]] + 1
# 更新当前字符的出现位置
char_dict[s[i]] = i
# 更新最长无重复字符子串的长度
max_len = max(max_len, i - start + 1)
# 返回最长无重复字符子串的长度
return max_len
```
希望对您有所帮助。
java实现无重复字符的最长子串
Java 实现无重复字符的最长子串可以使用滑动窗口算法。
算法流程如下:
1. 定义两个指针 left 和 right,分别表示滑动窗口的左右边界。
2. 从左边界开始,不断向右移动 right 指针,并将遍历到的字符加入到一个字典中,直到遇到重复的字符为止。
3. 当遇到重复的字符时,将左边界 left 向右移动,同时从字典中删除对应的字符,直到该字符不再重复为止。
4. 重复上述步骤 2 和 3,直到 right 指针遍历完整个字符串为止。
5. 每次移动结束后,更新当前最长不重复子串的长度,并记录对应的子串。
最终,得到的最长不重复子串即为所求。
以下是 Java 实现的代码示例:
```
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
} else {
set.remove(s.charAt(i++));
}
}
return ans;
}
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![php](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)