3. Longest Substring Without Repeating Characters

题目

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.

分析

给出一个字符串,找出最长无重复字符的子串的长度。

这个题目的一般思路是找到最长无重复字符的子串,然后求出长度。perfect,解决!思路很简单,但是做起来很麻烦。有很多条件需要去判断,而且时间复杂度不可能是O(n)。

这时候同学给我了我一个思路:能不能从字符的ASCII码着手。
把字符的ASCII的值当作数组下标,而数组的值记录该字符的位置;当遇到相同字符时,先去检测现在的长度和之前的长度哪个更长,记录最长值即可,而且时间复杂度为O(N)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
public int lengthOfLongestSubstring(String s){
char[] chars = s.toCharArray();
int currentLength = 0;
int leftIndex = -1;
int rightIndex = -1;
int[] charIndex = new int[256];
for (int i = 0; i < chars.length; i++) {
if (rightIndex == -1
&& charIndex[chars[i]] == 0
&& (i == 0 || chars[i] != chars[0])) {
currentLength = currentLength + 1;
} else {
if (charIndex[chars[i]] < leftIndex) {
rightIndex = i;
} else {
rightIndex = i;
leftIndex = charIndex[chars[i]];
}
if ((rightIndex - leftIndex) > currentLength) {
currentLength = (rightIndex - leftIndex);
}
}
charIndex[chars[i]] = i;
}
return currentLength;
}
}

总结

  • 通过字符的ASCII码对字符串进行操作,可以解决很多关于字符串的问题;
  • 算法是简单而优雅的,当自己的代码越写越多,判断越来越多,要及时检查自己的思路是不是走偏了。