Description

3. Longest Substring Without Repeating Characters

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.

Constraints:

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

Answer & Explaining

int lengthOfLongestSubstring(char* s) {
    int n = strlen(s); //字串長度
    int maxLen = 0; //初始化
    int start = 0;
    int charIndex[128] = {0}; // ASCII字元陣列，範圍是0-127

    for (int end = 0; end < n; end++) {
        char c = s[end]; //end不斷迭代
        if (charIndex[c] > start) { // 更新start指針的位置
            start = charIndex[c];
        }
        // 更新當前字元的位置到charIndex中
        charIndex[c] = end + 1; // 存儲的index是end+1，這樣方便處理start移動
        // 計算當前長度並更新最大長度
        int currentLen = end - start + 1;
        if (currentLen > maxLen) {
            maxLen = currentLen;
        }
    }
    return maxLen;
}

Testing

#include <stdio.h>
#include <string.h>

int lengthOfLongestSubstring(char* s) {
    int n = strlen(s); //字串長度
    int maxLen = 0; //初始化
    int start = 0;
    int charIndex[128] = {0}; // ASCII字元陣列，範圍是0-127

    for (int end = 0; end < n; end++) {
        char c = s[end]; //end不斷迭代
        if (charIndex[c] > start) { // 更新start指針的位置
            start = charIndex[c];
        }
        // 更新當前字元的位置到charIndex中
        charIndex[c] = end + 1; // 存儲的index是end+1，這樣方便處理start移動
        // 計算當前長度並更新最大長度
        int currentLen = end - start + 1;
        if (currentLen > maxLen) {
            maxLen = currentLen;
        }
    }
    return maxLen;
}
// 測試函數
int main() {
    char s1[] = "abcabcbb";
    char s2[] = "bbbbb";
    char s3[] = "pwwkew";
    printf("字串 \"%s\" 中最長的不含重複字符的子串長度是 %d\n", s1, lengthOfLongestSubstring(s1));
    printf("字串 \"%s\" 中最長的不含重複字符的子串長度是 %d\n", s2, lengthOfLongestSubstring(s2));
    printf("字串 \"%s\" 中最長的不含重複字符的子串長度是 %d\n", s3, lengthOfLongestSubstring(s3));
    return 0;
}