LeetCode: Longest Substring Without Repeating Characters

Bài toán

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

Giải pháp

Đặt 1 key $left chặn phần tử đầu của substring không trùng lặp.

Loop qua từng ký tự. Nếu không tồn tại ký tự trong set các ký tự đã duyệt thì tiếp tục ký tự tiếp theo.

Nếu có tồn tại thì loại bỏ ký tự trong set và tăng khoá bên trái cho đến khi hết các ký tự lặp.

Mỗi step trên check lại kết quả độ dài lớn nhất với mỗi lần thay đổi.

Code PHP

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $single = [];
        $left = 0;
        $result = 0;

        for ($i = 0; $i < strlen($s); $i++) {
            while(array_key_exists($s[$i], $single)) {
                unset($single[$s[$l]]);
                $l = $l + 1;
            }

            $single[$s[$i]] = 1;
            $result = max($result, $i - $l + 1);
        }

        return $result;
    }
}

Độ phức tạp

Time Complexity: O(n)

Space Complexity: O(1) - Dù số lượng phần tử có tăng lên thì khoảng space dùng để xử lý trong hàm vẫn giữ nguyên.