03 Longest Substring Without Repeating Characters

Descreption

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

Longest Substring Without Repeating Characters - LeetCode

First Thought

I suppose the first thought that popped up was just do what human would do: Read one by one, save what you have encountered and update when the repeated character is showing up.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        int longest = 0, current = 0;
        int head = 0;
        int pot[256] = {0};

        for (char c : s) {
            if (!pot[c]) {
                pot[c] = 1;
                current += 1;
            }
            else {
                // update
                if (longest < current) longest = current;

                // trace back
                for (int f = head; ; ++f) { // search from header
                    if (s[f] == c) {        // and break when find the one
                        head = f+1;
                        break;
                    }
                    current -= 1;  // update minus length
                    pot[s[f]] = 0; // and clear the pot
                }
            }
        }

        if (longest < current) longest = current;
        return longest;
    }
};

Complexity Analysis

Time complexity: $O(n)$

The string can only be traversed twice: the first time is searching and the second time is tracing back, which will not have any overlap. So, the best is $O(n)$ and the worst might be $O(2n)$.

Space complexity: $O(1)$

Just 256+4 integers.

(I have checked out the solutions and only to find my solution not bad XD)

Improvement

The overall algorithm is good while having some details to be improved.

Current is not a necessary. Replacing it with head and tail pointer will avoid current–, to improve a little.

penway Wang
penway Wang
Mechanic Technical Director

My research interests include computer vision, artificial intelligence and software engineering. I am a FSAE race car crew member at the same time, designing suspension system.

Next
Previous