Longest Substring Without Repeating Characters - LeetCode

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

思路:从左向右遍历一遍S，对于S中的每一个字符，记录该字符上一次出现时的下标。对于首次出现的字符，该值为-1.

我们设置一个变量nearest，记录迭代过程中，当前重复出现过的字符中上一次出现的下标的最大值。

举个例子：假设S为abcbkokpi. 假设我们当前迭代到了‘a‘，目前还没有遇见重复出现过的字符，因此nearest为-1. 直到我们迭代到了下标为3的‘b‘，这时候‘b‘重复出现过了，上一次出现时的下标为1，这时我们令nearest为1. 接着，当我们迭代到下标为6的‘k‘时，‘k‘也重复出现了。它上一次出现的下标为4，比当前的nearest值1要大，因此nearest被更新为4。

接下来，要考虑的问题是如何寻找最长的不含重复字符的连续子串。

假设当前我们迭代到的下标为i，字符s[i]上一次出现过的下标用pre[s[i]]表示。如果pre[s[i]]不大于nearest，则没有矛盾，我们更新pre[s[i]]为i后继续考虑下一位字符。假如说pre[s[i]]大于nearest，那么说明下标为pre[s[i]] ... i的这一段子串首尾字符是重复的，但是除去首尾的字符，中间没有任何重复，这时我们找到了一个长度为i - 1 - pre[s[i]]的不含重复字符的连续子串。我们用res来记录迭代过程中遇见到的最大的不含重复字符的连续子串长度，最后返回res即可。这里要注意，当我们迭代到S串的最后一位时，如果pre[s[i]]不大于nearest，则不含重复字符的连续子串长度为i - pre[s[i]]。因为这种情况下，最后一位字符可以出现在所求的子串中。

算法时间复杂度为O(n)

 1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         if (s == "") return 0;
 5         vector<int> pre(256, -1);
 6         int nearest = -1;
 7         int res = 1;
 8         for (int i = 0, n = s.size(); i < n; i++)
 9         {
10             if (n - 1 - nearest <= res) break;
11             int val = (int)s[i];
12             if (pre[val] > nearest || i == n - 1)
13             {
14                 int cand = i - nearest;
15                 if (pre[val] > nearest) cand--;
16                 res = max(res, cand);
17                 nearest = pre[val];
18             }
19             pre[val] = i;
20         }
21         return res;
22     }
23 };

Longest Substring Without Repeating Characters - LeetCode

原文：http://www.cnblogs.com/fenshen371/p/5096032.html