0003. Longest Substring Without Repeating Characters

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

Description

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

Example 1:

**Input:** s = "abcabcbb"
**Output:** 3
**Explanation:** The answer is "abc", with the length of 3.

Example 2:

**Input:** s = "bbbbb"
**Output:** 1
**Explanation:** The answer is "b", with the length of 1.

Example 3:

**Input:** s = "pwwkew"
**Output:** 3
**Explanation:** The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

**Input:** s = ""
**Output:** 0

Constraints:

• 0 <= s.length <= 5 * 104

• s consists of English letters, digits, symbols and spaces.

AC1: Sliding window, template

A template applicale to its evolved versions.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // edge cases
        if (s == null || s.length() == 0) return 0;

        // build note/map
        int[] note = new int[256];

        // walk string
        int l = 0, r = 0, repeat = 0, lgst = 0;
        for (; r < s.length(); r++) {
            char c = s.charAt(r);
            note[c]++;
            if (note[c] > 1) repeat++; // update counter, to validate window

            // window is qualifying
            while (repeat > 0) {
                lgst = Math.max(lgst, r - l); // record current substring length
                // move window
                note[s.charAt(l)]--;
                if (note[s.charAt(l)] == 1) repeat--;
                if (l >= r) break;
                l++;
            }
        }
        // r hit the end?
        lgst = Math.max(lgst, r - l);

        // result
        return lgst;
    }
}

AC2: Sliding window, regular

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> last_seen_pos(256, -1);
        int cursor = -1, max_len = 0;
        for (int i = 0; i < s.length(); i++) {
            if (last_seen_pos[s[i]] > cursor) {
                cursor = last_seen_pos[s[i]];
            }
            last_seen_pos[s[i]] = i;
            max_len = max(max_len, i - cursor);
        }
        return max_len;
    }
};