---
# System prepended metadata

title: Leetcode 3. Longest Substring Without Repeating Characters (C語言)

---

# 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)