[C++] Leetcode 3. Longest Substring Without Repeating Characters (Hint, Solution, Time and Space Complexity)

Problem

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

Longest Substring Without Repeating Characters - LeetCode

 

 

 

Hint

You can use a sliding window approach.
Think about what you should do when you find a repeating character.

 

 

 

Solution

 

 

 

Code

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        string str;
        int answer = 0;
        for (char c : s) {
            auto index = str.find(c);
            if (index != string::npos) {
                str += c;
                str.erase(0, index+1);
            } else {
                str += c;
                answer = max(answer, (int)str.size());
            }
        }

        return answer;
    }
};

 

 

 

Complexity

Time

Time complexity will be O(n^2).

 

Space

Space complexity will be O(n).

 

 

 

Best Solution (Pinned)

 

 

 

Overall