[LeetCode] 003. Longest Substring Without Repeating Characte

索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)Github: https://github.com/illuz/leetcode

003.Longest_Substring_Without_Repeating_Characters (Medium)链接：

题目：https://oj.leetcode.com/problems/Longest-Substring-Without-Repeating-Characters/代码(github)：https://github.com/illuz/leetcode

题意：

从标题就可以知道题意了，是求一个字符串中最长的不含重复字符的子串。

分析：

开一个数组记录当前字符最近出现的位置，，一遍算过去，更新左边界，用它计算最大值就行了。需要花费常数的空间。

代码：

C++:

class Solution {public:int lengthOfLongestSubstring(string s) {int maxlen = 0, left = 0;int sz = s.length();int prev[N];memset(prev, -1, sizeof(prev));for (int i = 0; i < sz; i++) {if (prev[s[i]] >= left) {left = prev[s[i]] + 1;}prev[s[i]] = i;maxlen = max(maxlen, i – left + 1);}return maxlen;}};

Java:

public class Solution {public int lengthOfLongestSubstring(String s) {int res = 0, left = 0;int prev[] = new int[300];// init prev arrayfor (int i = 0; i < 300; ++i)prev[i] = -1;for (int i = 0; i < s.length(); ++i) {if (prev[s.charAt(i)] >= left)left = prev[s.charAt(i)] + 1;prev[s.charAt(i)] = i;if (res < i – left + 1)res = i – left + 1;}return res;}}

Python:

class Solution:# @return an integerdef lengthOfLongestSubstring(self, s):res = 0left = 0d = {}for i, ch in enumerate(s):if ch in d and d[ch] >= left:left = d[ch] + 1d[ch] = ires = max(res, i – left + 1)return res

当你开展的事业从事的行动穷途末路大势已去的时候，