博文中会简要介绍Leetcode P0003题目分析及解题思路。
“Longest Substring Without Repeating Characters”是一道非常经典并且高频出现于面试的题目，题干易懂。要求找到最长不含重复字符的子串。
Given a string, find the length of the longest substring without repeating characters
可以预料复杂度是O(n)，使用滑动窗口的思想，控制左右指针之间的窗口内始终满足约束条件，即无重复字符。根据右指针扫描的对象来判断是否需要左指针，最终只需要右指针扫描到字符串末尾即可以得到最长无重复字符的子串的长度。
滑动窗口的思想在面试中十分常见，主要在于控制窗口内的序列（子串）合法。实现这一强约束的核心任务在于控制左指针移动。在移动左指针的时候要满足，移动结束后窗口内恰好合法，也就是任何一次少移都会导致不合法，任何一次多移都会导致非最优解。而移动左指针的时机一般取决于右指针当前指向的对象是否会将窗口的合法状态转化为不合法，如果会，则需要移动左指针来保持窗口合法，不会则持续移动右指针。
这一题还使用了cache思维，即用HashTable来存储窗口内信息，通过借助HashTable来查询窗口是否满足合法性约束。
以下是Java的题解代码实现。
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0)
return 0;
Map<Character, Integer> char2IndexMap = new HashMap<>();
int left = 0, right = 1, maxLen = 1;
char[] chars = s.toCharArray();
char2IndexMap.put(chars[left], left);
while (right < chars.length) {
if (char2IndexMap.containsKey(chars[right])) {
maxLen = Math.max(maxLen, right-left);
int end = char2IndexMap.get(chars[right]);
while (left < end + 1) {
char2IndexMap.remove(chars[left]);
++left;
}
}
char2IndexMap.put(chars[right], right);
++right;
}
return Math.max(maxLen, right-left);
}
}
以下是C++的题解代码实现。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.length() == 0)
return 0;
unordered_map<char, int> char2index_map;
int left = 0, right = 1, max_len = 1;
char2index_map[s[left]] = left;
while (right < s.length()) {
if (char2index_map.count(s[right]) > 0) {
max_len = max(max_len, right-left);
int end = char2index_map[s[right]];
while (left < end + 1) {
char2index_map.erase(s[left]);
++left;
}
}
char2index_map[s[right]] = right;
++right;
}
return max(max_len, right-left);
}
};