3 Longest Substring Without Repeating Characters
题目:
即找到最大无重复字母的子串。
考虑思路:
1)以键值对的形式存储字符串。其中,以字符为键,其索引为值。
根据键的唯一性,我们可以知道该hashmap表中存储的是字符串的全部不重复的字符。
2)遍历字符串时,首先设置滑动窗口,当遍历到S[i]到S[j]之间时,如果存在与S[j+1]相同的字符S[k],记录下此时得到的不重复子串的长度j+1-k。并且将窗口的左端移动到k,并且,即重新往后遍历,直到找到与窗口内存在重复的字符时,再重复上述步骤。
3)如果该字符为新的不重复的字符,那么就压入hashmap。
几种情况:
1)对于类似“au”这种,无重复的字符串,最大子串的长度根据字符串的长度时刻进行更新。假设当前读到索引为i的字符,那么此时的最大子串为i+1-index,其中index为0。
2)对于类似“abcabca”这种存在重复的子串,最大子串的长度更新如下。假设当前遍历的是s[0]-s[2]之间的字符串,与1)的过程类似,当遍历到s[3]时,发现hashmap中已经存在键为a的值了,那么此时index就为hashmap中键a对应的value,也就是其索引号,同时更新最大子串长度为Math.max(i+1-index,max)。