1.原題
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.
2.題意
給定一個(gè)字符串泉哈，找出其最大的子串蛉幸，子串不包含重復(fù)字符。
3.思路
- 首先丛晦，什么是子字符串奕纫，什么是子序列，子串代表的是原字符串中連續(xù)的字符烫沙，而子序列代表的是子序列不需要是挨著的匹层，只要是在原字符串中也是這樣的先后順序。舉個(gè)例子斧吐，比如pwwkew又固，wke是子串，而pwke只是子序列
- 其次煤率，題目的一個(gè)重要的要求是仰冠，子串中不能有重復(fù)元素
- 做法是，我們從第一個(gè)元素開(kāi)始往后掃描蝶糯，一邊掃描洋只，一邊保存一個(gè)hash表，這個(gè)表記錄的是截止到當(dāng)前的字符在原字符串中的位置（下標(biāo)）。
- 當(dāng)我們掃描到某個(gè)字符识虚，發(fā)現(xiàn)該字符在上一個(gè)子串中已經(jīng)存在了肢扯，我們更新hash表中該字符的下標(biāo)，并查看當(dāng)前的子字符串是不是長(zhǎng)度當(dāng)前最大担锤。
- 舉例蔚晨，比如對(duì)于pwwkew，
- 掃描p記錄p對(duì)應(yīng)的下標(biāo)p->0,
- 掃描w同樣記錄w->1,
- 繼續(xù)掃描時(shí)發(fā)現(xiàn)w已經(jīng)在上一個(gè)字符串中出現(xiàn)了肛循，那么上一個(gè)字符串的長(zhǎng)度就是2铭腕，更新下當(dāng)前最大的子串長(zhǎng)度到2.
- 這個(gè)時(shí)候開(kāi)啟了新的子串，
- w的下標(biāo)是w->2,
- 然后掃描k：k->3,
- 繼續(xù)多糠，e->4累舷，
- 接下來(lái)又掃描發(fā)現(xiàn)了w，這個(gè)時(shí)候上一個(gè)子串到頭了夹孔，子串是wke被盈，長(zhǎng)度是3.更新當(dāng)前最大的子串長(zhǎng)度是3.
4.代碼如下
JAVA
class Solution {
public int lengthOfLongestSubstring(String s) {
int begin_index = 0;
int max = 0;
int[] mark = new int[256];
Arrays.fill(mark, -1);
for(int i = 0; i < s.length(); i++) {
int index = s.charAt(i);
if(mark[index] != -1 && mark[index] >= begin_index) {
max = max > (i - begin_index)?max: i - begin_index;
begin_index = mark[index] + 1;
}
mark[index] = i;
}
max = max > (s.length() - begin_index)?max: s.length() - begin_index;
return max;
}
}
Python
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
hash_table = []
for i in range(256):
hash_table.append(-1)
max_res = 0
begin_index = 0
for i in range(len(s)):
if hash_table[ord(s[i])] != -1 and hash_table[ord(s[i])] >= begin_index:
max_res = max(max_res, i - begin_index)
begin_index = hash_table[ord(s[i])] + 1
hash_table[ord(s[i])] = i
max_res = max(max_res, len(s) - begin_index)
return max_res
