题目：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含'a'~'z'的字符。例如，在字符串"arabcacfr"中，最长的不含重复字符的子字符串是"acfr"，长度为4。
练习地址
https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
参考答案
public int longestSubstringWithoutDuplication(String str) {
if (str == null || str.length() == 0) {
return 0;
}
int curLength = 0, maxLength = 0;
int[] position = new int[26];
for (int i = 0; i < position.length; i++) {
position[i] = -1;
}
for (int i = 0; i < str.length(); i++) {
int prevIndex = position[str.charAt(i) - 'a'];
if (prevIndex < 0 || i - prevIndex > curLength) {
curLength++;
} else {
if (curLength > maxLength) {
maxLength = curLength;
}
curLength = i - prevIndex;
}
position[str.charAt(i) - 'a'] = i;
}
if (curLength > maxLength) {
maxLength = curLength;
}
return maxLength;
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
