# Leetcode 3. Longest Substring Without Repeating Characters (C語言)
- 題目
Given a string, find the length of the longest substring without repeating characters.
- 範例
Input: "pwwkew"
Output: 3
Explanation: 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.
```c=
int lengthOfLongestSubstring(char * s){
int *ht=(int*)malloc(128*sizeof(int)),i;
for(i=0;i<127;i++){
ht[i]=-1; //都先初始化成-1
}
int max=0,strsize=strlen(s),substring_start=0;
for(i=0;i<strsize;i++){
if((ht[s[i]])>=substring_start){ //在子字串裡了
substring_start=ht[s[i]]+1;
ht[s[i]]=i;
}
else{ //不在子字串裡
ht[s[i]]=i;
if(i-substring_start+1>max)max=i-substring_start+1;
}
}
return max;
}
```
思路:讀取一個字元,看有沒有在substring裡,
1. 該字元不在substring內,加進substring且比較max大小,比max大則更新max。
2. 該字元在substring內,更新substring。
e.g. 當字串==s=abca== ==substring=abc== 則再讀到==a==時,更新子字串成==bca==
至於怎麼看有沒有在substring內,可宣告一個Array,其index是該字元,對應到的==value==則是他==在string內的index==(即hash table的用法)
e.g. 若Array[97]=1,則表示字元'a'在string內的index是1。
(根據[ASCII code](https://zh.wikipedia.org/wiki/ASCII) 字元'a'對應到十進位的97)
且搭配一個substring_start 表示substring開頭的第一個字元之index。比較index有沒有超過開頭就知道在不在目前的子字串內了
e.g. ==s=abaab== 讀到第三個a時 substring會被更新成a(==即substring_start=3==),此時再讀到b,==ht[b]=1<3=substring_start==,故b不再substring內,加入substring。
![](https://i.imgur.com/aV9croL.png)