# 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 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
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
###### 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.

Previous