LeetCode 3. Longest Substring Without Repeating Characters ( C )-Medium

題目為給定一個字串，尋找其中最長的子字串，並且此子字串不得有重複之字元。

題目與範例如下

Given a string s, find the length of the longest substring without repeating characters.



Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Example 4:

Input: s = ""
Output: 0
 

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces

我採用的策略為，使用一個變數紀錄子字串的起始點，子字串的終止點為目前尋訪到的字元，並逐次檢查新加入的字元是否與子字串內的字元有重複，有則把子字串的起始點設為重複的下一個，每次比較是否比記錄中的最長長度還長。

下方為我的程式碼

void comparechar(char *str,char target,int *submin, int *submax){
    for(int i = *submin ; i < *submax ; i++ ){
        if(str[i] == target){
            *submin = i+1;
            break;
        }
    }
}

int lengthOfLongestSubstring(char * s){
    int index = 0,submin = 0,max = 0;
    while(s[index] != '\0'){
        comparechar(s,s[index],&submin,&index);
        if(index - submin + 1 > max)
            max = index - submin + 1;
        index++;
    }
    return max;
}

comparechar函式，為逐一比較新加入的字元是否存在子字串內，如重複則改變子字串的起始位置。

主函式為逐一字元傳入comparechar，並檢查目前的長度是否超過最大值，我這次變數大部分採用傳參的方式傳遞，以減少記憶體使用量。

下面為時間與空間之消耗

Runtime: 4 ms, faster than 85.25% of C online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 5.9 MB, less than 65.47% of C online submissions for Longest Substring Without Repeating Characters.

下一題連結 : LeetCode 4. Median of Two Sorted Arrays ( C )-Hard