#Longest Substring Without Repeating Characters

12 messages · Page 1 of 1 (latest)

devout adder
#

For reference: https://leetcode.com/problems/longest-substring-without-repeating-characters/

So I actually managed to solve this without implementing a full fledged hash table and all testcases succeed except for the last one.
The algorithm that I chose to go with is the one that is hinted: "Generate all possible substrings & check for each substring if it's valid and keep updating maxLen accordingly."

Now the last testcase is a very long one with a lot of duplicate lines on which my solution times out. Is there any way to optimize my solution so that I don't have to use some sort of ugly hardcoded solution for this special test case or use another algorithm altogether?

Thanks in advance

sacred orbitBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

devout adder
#

And of course I forget to post my actual implementation:

bool is_valid(char *s, int start, int end);

int lengthOfLongestSubstring(char* s) {
    int len = strlen(s);
    int maxlen = 0;

    for (int start = 0; start < len; start++) {
        for (int end = start; end < len; end++) {
                if(is_valid(s, start, end)) {
                    int n = end - start + 1;
                    maxlen = maxlen > n ? maxlen : n;
                }
        }
    }
    return maxlen;
}

bool is_valid(char *s, int start, int end) {
    char alphabet[127];
    memset(alphabet, 0, 127);

    for (int i = start; i <= end; i++) {
        if (alphabet[s[i]] == 0)
            alphabet[s[i]] = 1;
        else
            return false;
    }
    return true;
}
wintry rapids
# devout adder For reference: https://leetcode.com/problems/longest-substring-without-repeating...

If you look at your code you can probably tell that you're doing three loops that are able to go from the very start to the very end of the string (not all at the same time, but that can be ignored), so it's like you're looping over the array inside of a loop over the array inside of a loop over the array. This is expressed with an order/time complexity O(n^3). So you have an n cubed time complexity program here.

Tip: the first and second loop are essential, but the third one is recreating the entire hash table when you just add a single character to the end in the second loop.

If you merge is_valid() its code back into lengthOfLongestSubstring(), it should make it much easier to tell that you're doing an unnecessary third loop. This is an excellent example of the danger of abstracting code into a new function; it becomes significantly harder to get these epiphanies. :)

#

You could put static in front of the alphabet table (or move it outside of the function so that it becomes a global variable, it's equivalent, apart from the static only being accessible in the one function it's in), since your current code is unnecessarily recreating the space for it every time. Accessing a global might be slightly slower though, so try to profile (time) the difference between using and not using static, if you know how to. (perf on Linux is amazingly simple and well-suited for this, as it is often already installed)

#

I'd personally also let alphabet be an array of bool instead of char by the way, since it's more expressive of the char only ever being 0 or 1 in your program. You can then also use true and false in your program (and I personally recommend never leaving out the curly braces, since otherwise accidental weird space/tab indentation can mislead people into thinking something's inside of an if-statement while it's not, while curly braces are explicit):

if (alphabet[s[i]]) {
    return false;
} else {
    alphabet[s[i]] = true;
}
devout adder
sacred orbitBOT
#

@devout adder Has your question been resolved? If so, type !solved :)

devout adder
#

!solved

sacred orbitBOT
#

Thank you and let us know if you have any more questions!

This thread is now set to auto-hide after an hour of inactivity

wintry rapids
devout adder
#

This was my final solution that didn't time-out:

int lengthOfLongestSubstring(char* s) {
    int len = strlen(s);
    int maxlen = 0;
    bool alphabet[127];

    for (int start = 0; start < len; start++) {
        memset(alphabet, 0, 127);
        for (int end = start; end < len; end++) {
            if (alphabet[s[end]] == false) {
                alphabet[s[end]] = true;
            } else {    
                break;
            }
            
            int n = end - start + 1;
            maxlen = maxlen > n ? maxlen : n;
        }
    }
    return maxlen;
}