Unable to find the bug in leetcode problem

user_7451099 0
Viewed 64

The problem statement:

"Longest Substring Without Repeating Characters"

Input: "hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789hijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

Expected output: 55

Actual Output: 312

#include <stdio.h>

int lengthOfLongestSubstring(char *s) {
    int i = 0;
    char arr[255];
    int max = 0;
    memset(arr, -1, 255);
    int si = 0; //substring start index
    while (s[i] != '\0') {
        if (arr[s[i]] != -1) {
            int psi = si;  //previous substring start
            int pi = arr[s[i]]; //previous index of s[i]
            si = pi + 1;  //new substring starts
            int psl = i - psi; //previous substring length
            max = max > psl ? max : psl;
            for(int j = psi; j <= pi; j++) {
                arr[s[j]] = -1;
            }
        }
        arr[s[i]] = i;
        i++;
    }
    max = max > (i - si) ? max : (i - si);
    return max;
}

int main(int argc, char **argv) {
    //printf("%s\n", argv[1]);
    printf("%d\n", lengthOfLongestSubstring(argv[1]));
    return 0;
}
data-structures c algorithm
1 Answers

There are multiple problems in your code:

  • the array used to store offsets in the string has type char, which has a limited range and might not be signed. Using -1 as a special value will not work is the char type is unsigned by default and your method will not work for strings longer than CHAR_MAX, which may be as small as 127.

  • you call memset() without a proper definition as you do not include <string.h>.

  • the array is defined with a length of 255, which does not allow for the maximum byte value of 255.

  • indexing it with a char value is risky as non ASCII characters may have a negative value, hence index outside the boundaries of the array.

Here is a modified version:

#include <stdio.h>

// assuming 8-bit bytes
int lengthOfLongestSubstring(const char *s) {
    int arr[256];
    int i;
    int max = 0;
    for (i = 0; i < 256; i++) {
        arr[i] = -1;
    }
    int si = 0; //substring start index
    for (i = 0; s[i] != '\0'; i++) {
        if (arr[(unsigned char)s[i]] != -1) {
            int psi = si;  //previous substring start
            int pi = arr[(unsigned char)s[i]]; //previous index of s[i]
            si = pi + 1;  //new substring starts
            int psl = i - psi; //previous substring length
            max = max > psl ? max : psl;
            for (int j = psi; j <= pi; j++) {
                arr[s[j]] = -1;
            }
        }
        arr[(unsigned char)s[i]] = i;
    }
    return max > (i - si) ? max : (i - si);
}

int main(int argc, char **argv) {
    if (argc > 1) {
        printf("%d\n", lengthOfLongestSubstring(argv[1]));
    }
    return 0;
}
user_45932670
Related