LeetCode 03. Longest Substring Without Repeating Characters

🧩 PROBLEM - LeetCode 03. Longest Substring Without Repeating Characters

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

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

Example.

[1]

Input: s = “abcabcbb”

Output: 3

Explanation: The answer is “abc” or “bca” or “cab” with the length of 3.

Constraints:

0 <= s.length <= 5 * $10^4$

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

---

Problem anaylsis

1. string datatype is “char”
2. The characters ranges on 0~255, not over 1 byte.
3. length is 50,000, it is not big if time complex is under O(n) or O(n $\log{n}$)
4. This problem focus on just Max length, not include index
5. I should check to conflict same letter, so considering bit-mask

EX1) abcabcbb

a b c
1 2 3

-> conflict -> a      b c       -> a b c
 
               1(->4) 2 3       =  3 1 2

               --> it means, if i can check conflict, revaluing previous and current letters.

EX2) pwwkew

p w
1 2

-> conflict ->  p w         -> p w 
                1 2(->3)    =  0 1

                --> it means, if i should be renew all of things, making reset all value and restart current value.

This progress is we record order of letter and the lastest value is highest local max. but when we meet same value that we already met, revalue all of letters. All of times, I should renew “local max” and then compare “global max” and “local max”.

Rule of LOCAL MAX

1. We meet a letter at first time. The letter value is recorded by local max value.
2. When we meet the letter that we already met, the current letter value is standard value that all of things are renewed. The value will be minus every value and if some letter values are under 0, the value fixed 0 (it means, not anymore including array).

Result 4 ~ 8ms

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
            int arrI32Flags[256] = { 0 };
            int i32Length = s.length();

            int i32Max = 0;
            int i32LocalMax = 0;
            const char* pI8Pointer = s.c_str();

            for (int i = 0; i < i32Length; ++i)
            {
                uint8_t u8 = (uint8_t)*pI8Pointer;
                i32LocalMax++;

                if (arrI32Flags[u8] == 0)
                    arrI32Flags[u8] = i32LocalMax;
                else
                {
                    int i32Minus = arrI32Flags[u8];
                    arrI32Flags[u8] = i32LocalMax;

                    for (int j = 0; j < 256; ++j)
                    {
                        if (arrI32Flags[j] > 0)
                            arrI32Flags[j] = arrI32Flags[j] - i32Minus < 0 ? 0 : arrI32Flags[j] - i32Minus;
                    }

                    i32LocalMax = arrI32Flags[u8];
                }

                i32Max = std::max(i32Max, i32LocalMax);
                ++pI8Pointer;
            }

            return i32Max;
    }
};

Result 0 ~ 3ms

Additional optimizing -> Guess what get more better cache-hit during if statement.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
            int arrI32Flags[256] = { 0 };
            int i32Length = s.length();

            int i32Max = 0;
            int i32LocalMax = 0;
            const char* pI8Pointer = s.c_str();

            for (int i = 0; i < i32Length; ++i)
            {
                uint8_t u8 = (uint8_t)*pI8Pointer;
                i32LocalMax++;

                if (arrI32Flags[u8] > 0)
                {
                    int i32Minus = arrI32Flags[u8];
                    arrI32Flags[u8] = i32LocalMax;

                    for (int j = 0; j < 256; ++j)
                    {
                        if (arrI32Flags[j] > 0)
                            arrI32Flags[j] = arrI32Flags[j] - i32Minus < 0 ? 0 : arrI32Flags[j] - i32Minus;
                    }

                    i32LocalMax = arrI32Flags[u8];
                }
                else
                    arrI32Flags[u8] = i32LocalMax;

                i32Max = std::max(i32Max, i32LocalMax);
                ++pI8Pointer;
            }

            return i32Max;
    }
};

Two codes are same except order of if statment. but the cache-hit and miss effect the performance. Upper code is 7ms, lower code is 0ms.

When we are programming some issue, thinking about what progress will be more repeated.

---

---

Anaylsis

• CHECK SCOPE -> INPUT SIZE
  • Under Hundred: O($2^n$)
  • Under thousand : O($n^2$)
  • Under 10K: O(N $\log{N}$)
  • Under 1M ~ over: O( $\log{n}$)
• COMPLEXITY
  • Time complexity
  • Space complexity
• Check Valid DataType
  • Overflow
• SIMULATION
  • Check test case by myself
• Compare with other people solutions

---

---

Slow but easy

class Solution 
{
public:
    int lengthOfLongestSubstring(std::string s) 
    {
        int i32Result = 0;
        std::unordered_set<char> setWindow;
        int i32Left = 0;
        int i32Right = 0;

        for (int i = 0; i < (int)s.size(); i++) 
        {
            while (setWindow.count(s[i])) 
            {
                setWindow.erase(s[i32Left]);
                i32Left++;
            }

            setWindow.insert(s[i]);
            i32Result = std::max(i32Result, i - i32Left + 1);
        }

        return i32Result;
    }
};