题目
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc"，其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b"，其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke"，其长度为 3。
请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。
解题思路
首先想到的是穷举法，即把所有的可能的组合通过对字符串进行两次遍历，找到其最长无重复的子序列；不过此问题显然不是需要一个时间复杂度如此之高的算法。 如果是人工来找，会使用一个滑动窗口一样的东西从左依次往右查找，这个滑动窗口随时变化大小，里面存储无重复的序列，同时需要记录一个最大的序列个数；
使用一个map记录每个字符出现的位置，一个重复位置的标志位和一个最大长度的计数器；遍历字符串，记录每个字符串的位置到map中，如遇重复，则更新重复位置，同时更新此字符的位置；每次做一个大小判断取出最大的子序列长度
解法
# ruby解法
# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
ans = 0 # 表示最大的子序列长度
re_pos = 0 # 表示最后一次出现重复的位置
map = {}
s.split('').each_with_index do |c, i|
now_pos = i + 1 # 当前位置
unless map[c].nil?
re_pos = [map[c], re_pos].max
end
ans = [ans, now_pos - re_pos].max
map[c] = now_pos
end
ans
end
/**
* java解法
* @param {String} s
* @return {Integer}
*/
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0, rePos=0;
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
int nowPos = i + 1;
if (map.containsKey(s.charAt(i))) {
rePos = Math.max(map.get(s.charAt(i)), rePos);
}
ans = Math.max(ans, nowPos - rePos);
map.put(s.charAt(i), nowPos);
}
return ans;
}
// 官方答案
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) {
// try to extend the range [i, j]
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;
}
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128]; // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}