Leetcode 3 Solution

Leetcode Question Link

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

Thinking Process

This question can be easily done if we target at O(N^3). Just pick any left and right pairs, and then check if this is a substring without repeating characters.

To optimize that, we can select a fixed right position, and then scan all the way to the left until the current substring has a repeating characters. This solution can run within O(N^2).

Can we make it better? Yes, we can.

For any substring or subarray problem, we should always try the idea of sliding window. In this case, we can iterate the array. As we are iterating, the current index is treated as the end of the substring, and then we try to find the minimum left position (the start of the substring). Let’s assume that is L(i).

• Apparently, L(0) = 0.
• When i > 0, we know the longest substring end from i - 1. We are now adding a new character s[i] to that string.
  • If s[i] does not exist in the subtring from L(i - 1) to i - 1, we know that the subtring from L(i - 1) to i is a substring that does not have repeating characters.
  • If s[i] does exists in the substring from L(i - 1) to i - 1, we’ll need to find out its last appearing position (say j), and then we can make L(i) as j + 1. Doing a linear search definitely can do that, but since there are only 26 possible characters, using a map to memorize each characters’ last appearing positions can help us find it in O(1) time.

Time & Space Complexity

Assuming N is the size of the array, the time & space compelxities are:

• Time complexity: O(N)
• Space complexity: O(N)

Solution

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int pos[256];
        for (int i = 0; i < 256; i++)
            pos[i] = -1;

        int max_len = 0;
        int l = 0;

        for (int i = 0; i < s.size(); i++)
        {
            char ch = s[i];

            l = max(l, pos[ch] + 1);
            pos[ch] = i;

            max_len = max(max_len, i - l + 1);
        }

        return max_len;
    }
};

Learnings

• Think about sliding windows whenever you see a substring or subarray problem.