Question

How to find the longest substring without repeating characters in C

Answer 1

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

/*
 * Finds the longest substring without repeating characters.
 * This version keeps a presence table and shrinks the window
 * by clearing characters until the duplicate is removed.
 *
 * Time complexity: O(n)
 */
const char* longest_unique_substring_ascii(const char *str, int *out_len) {
    int n = strlen(str);

    int seen[256] = {0};   // 0 = not in window, 1 = in window
    int left = 0, right = 0;
    int best_left = 0, best_right = 0;

    while (right < n) {
        unsigned char c = str[right];

        if (seen[c]) {
            // Shrink window until we remove the duplicate
            while (str[left] != c) {
                seen[(unsigned char)str[left]] = 0;
                left++;
            }
            left++; // skip the duplicate itself
        } else {
            seen[c] = 1;

            if (right - left > best_right - best_left) {
                best_left = left;
                best_right = right;
            }
        }

        right++;
    }

    *out_len = best_right - best_left + 1;
    
    return str + best_left;
}

int main() {
    const char *str = "xwwwqfwwxqwyq";

    int len = 0;
    const char *result = longest_unique_substring_ascii(str, &len);

    printf("Input: %s\n", str);
    printf("Longest substring without repeating characters: ");
    fwrite(result, 1, len, stdout);
    printf("\n");

    return 0;
}


/*
run:

Input: xwwwqfwwxqwyq
Longest substring without repeating characters: xqwy

*/

 

70+ SQL courses for beginners and professionals

Answer 2

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

/*
 * Finds the longest substring without repeating characters.
 * Uses a sliding window and a table of last-seen indexes.
 *
 * - last_seen[c] stores the most recent index of character c.
 * - left/right define the current window.
 * - When a duplicate is found inside the window, move left forward.
 *
 * Time complexity: O(n)
 */
const char* longest_unique_substring(const char *str, int *out_len) {
    int n = strlen(str);

    // Last-seen index for each ASCII character; -1 means "not seen"
    int last_seen[256];
    for (int i = 0; i < 256; i++) last_seen[i] = -1;

    int left = 0;
    int best_start = 0;
    int best_len = 0;

    for (int right = 0; right < n; right++) {
        unsigned char c = str[right];

        // If character was seen inside the current window, move left
        if (last_seen[c] >= left) {
            left = last_seen[c] + 1;
        }

        // Update last-seen index
        last_seen[c] = right;

        // Check if this window is the best so far
        int window_len = right - left + 1;
        if (window_len > best_len) {
            best_len = window_len;
            best_start = left;
        }
    }

    *out_len = best_len;
    return str + best_start;
}

int main() {
    const char *str = "xwwwqfwwxqwyq";

    int len = 0;
    const char *result = longest_unique_substring(str, &len);

    printf("Input: %s\n", str);
    printf("Longest substring without repeating characters: ");
    fwrite(result, 1, len, stdout);
    printf("\n");

    return 0;
}


/*
run:

Input: xwwwqfwwxqwyq
Longest substring without repeating characters: xqwy

*/

 

70+ SQL courses for beginners and professionals