输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
class Solution {
public int lengthOfLongestSubstring(String s) {
// 判空
if (s.length() == 0)
return 0;
// 状态转移方程
// dp[i] 表示以字符 s[i] 结尾的「最长不重复子字符串」的长度
int[] dp = new int[s.length()];
// 使用哈希表统计「每个字符最后一次出现的位置」
Map<Character, Integer> hashmap = new HashMap<>();
// 最长不含重复字符的子字符串的长度
int ans = 0;
// i 为左边界，j 为右边界
for (int j = 0; j < s.length(); j++) {
// 从哈希表中获取到当前字符 s[j] 左边距离最近的相同字符 s[i]
// 左边不存在相同的字符就给 i 赋值 -1
int i = hashmap.getOrDefault(s.charAt(j), -1);
// 遍历字符串的同时使用哈希表统计「每个字符最后一次出现的位置」
hashmap.put(s.charAt(j), j);
// 状态转移方程
if (j!=0)
dp[j] = dp[j - 1] < j - i ? dp[j - 1] + 1 : j - i;
else
dp[j] = 1;
// 更新结果
ans = Math.max(ans, dp[j]);
}
return ans;
}
}
class Solution {
fun lengthOfLongestSubstring(s: String): Int {
// 判空
if (s.length == 0)
return 0
// 状态转移方程
// dp[i] 表示以字符 s[i] 结尾的「最长不重复子字符串」的长度
val dp = IntArray(s.length)
// 使用哈希表统计「每个字符最后一次出现的位置」
val hashmap = mutableMapOf<Char, Int>()
// 最长不含重复字符的子字符串的长度
var ans = 0
// i 为左边界，j 为右边界
for (j in 0 until s.length) {
// 从哈希表中获取到当前字符 s[j] 左边距离最近的相同字符 s[i]
// 左边不存在相同的字符就给 i 赋值 -1
val i = hashmap.getOrDefault(s[j], -1)
// 遍历字符串的同时使用哈希表统计「每个字符最后一次出现的位置」
hashmap[s[j]] = j
// 状态转移方程
if (j != 0)
dp[j] = if (dp[j - 1] < j - i) dp[j - 1] + 1 else j - i
else
dp[j] = 1
// 更新结果
ans = Math.max(ans, dp[j])
}
return ans
}
}
