Longest Substring Without Repeating Characters

Q: Sự khác nhau giữa chuỗi con và dãy con là gì?

Chuỗi con (substring) là một khối ký tự nằm cạnh nhau, như ode trong coddycode . Dãy con (subsequence) có thể bỏ qua một số ký tự, như cdy . Bài toán này yêu cầu tìm chuỗi con, vì vậy ta có thể dùng một cửa sổ với hai đầu.

Trung bìnhCửa sổ trượt Băm

+10

Bạn nhận được một chuỗi s. Hãy tìm chuỗi con dài nhất, tức là một dãy ký tự nằm liền kề nhau, trong đó không có ký tự nào xuất hiện hai lần, rồi trả về độ dài của chuỗi đó.

Chữ cái viết hoa và viết thường được tính là các ký tự khác nhau, vì vậy a và A không bị xem là ký tự lặp lại.

Hàm

lengthOfLongestSubstring(s: string) → integer

sstring: chuỗi cần tìm
Trả vềinteger: độ dài của chuỗi con dài nhất không có ký tự nào lặp lại

Ràng buộc

1 ≤ s.length ≤ 5 × 10⁴
s chỉ chứa các chữ cái tiếng Anh (chữ thường và chữ hoa) và chữ số.
Chữ cái viết hoa và viết thường là các ký tự khác nhau.

Ví dụ

Đầu vào: s = "coddycode"
Đầu ra: 5
Giải thích: ycode chứa năm ký tự khác nhau. Thêm d vào trước sẽ tạo thành dycode, trong đó có hai d, và mọi chuỗi nào khác gồm ít nhất năm ký tự đều có ký tự lặp lại.

Đầu vào: s = "racecar"
Đầu ra: 4
Giải thích: Cả race và ecar đều có bốn chữ cái khác nhau. Mỗi chuỗi gồm năm chữ cái đều có một chữ cái xuất hiện hai lần.

Đầu vào: s = "a1b2a3b"
Đầu ra: 5
Giải thích: Các chữ số cũng được tính là ký tự, vì vậy 1b2a3 có năm ký tự khác nhau. Cả hai đoạn gồm sáu ký tự đều có thêm một a hoặc một b.

Câu hỏi mở rộng

Bạn sẽ thay đổi điều gì nếu s có thể chứa bất kỳ ký tự Unicode nào thay vì chỉ chữ cái và chữ số?

Lời giải

Duy trì một cửa sổ: hai đầu mút bao quanh một đoạn không có ký tự lặp lại. Đầu mút bên phải lần lượt đọc từng ký tự đúng một lần, còn đầu mút bên trái chỉ tiến về phía trước, vì vậy chỉ cần một lượt là tìm được đoạn dài nhất không có ký tự lặp lại kết thúc tại mỗi vị trí.

Kiểm tra từng chuỗi con

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Thử mọi vị trí bắt đầu và kết thúc, rồi kiểm tra từng chuỗi con bằng cách thêm các ký tự của nó vào một tập hợp cho đến khi gặp một ký tự đã có. Bạn sẽ kiểm tra mọi chuỗi con ứng viên, nên không thể bỏ sót chuỗi hợp lệ dài nhất.

Có khoảng n²/2 chuỗi con, tức 1.25 × 10^9 khi n = 5 × 10^4, và mỗi lần kiểm tra có thể đọc đến n ký tự: O(n³). Ở đây, mỗi lần kiểm tra dừng sau tối đa 63 ký tự vì chuỗi chỉ chứa 62 ký tự khác nhau, nhưng số lần kiểm tra vẫn vượt quá một tỷ.

Thuật toán

Đặt best thành 0.
Với mỗi chỉ số bắt đầu, duyệt qua mọi chỉ số kết thúc từ đầu đến cuối chuỗi.
Lần lượt thêm các ký tự của chuỗi con vào một tập hợp rỗng, rồi dừng lại khi gặp ký tự đầu tiên đã có trong tập hợp.
Nếu không có ký tự nào lặp lại và chuỗi con dài hơn best, hãy lưu độ dài của chuỗi con.
Trả về best.

def lengthOfLongestSubstring(s):
    def has_no_repeat(start, end):
        seen = set()
        for k in range(start, end + 1):
            if s[k] in seen:
                return False
            seen.add(s[k])
        return True

    best = 0
    n = len(s)
    for start in range(n):
        for end in range(start, n):
            if has_no_repeat(start, end):
                best = max(best, end - start + 1)
    return best

Cửa sổ trượt với tập hợp

Ý tưởng

Nếu abc không có ký tự lặp lại, để kiểm tra abcd, chỉ cần hỏi một câu: d có nằm trong a, b và c không? Một tập hợp các ký tự trong cửa sổ sẽ trả lời câu hỏi này ngay lập tức.

Di chuyển right từng bước một. Nếu ký tự mới nằm trong tập hợp, hãy xóa các ký tự từ bên trái cho đến khi loại bỏ bản sao trước đó của ký tự này, sau đó thêm nó vào và đo độ dài. Bạn chỉ xóa ký tự khi cần, vì vậy với mỗi right, cửa sổ là đoạn dài nhất không có ký tự lặp lại và kết thúc tại đó, còn chuỗi con dài nhất có thể kết thúc ở bất kỳ vị trí nào. Mỗi ký tự được thêm vào tập hợp một lần và rời khỏi tập hợp nhiều nhất một lần: O(n).

Thuật toán

Bắt đầu với một tập hợp rỗng, left = 0 và best = 0.
Di chuyển right qua mọi chỉ số.
Khi s[right] có trong tập hợp, xóa s[left] rồi tăng left lên một bước.
Thêm s[right] vào tập hợp.
Nếu right - left + 1 lớn hơn best, hãy lưu giá trị đó.
Trả về best.

def lengthOfLongestSubstring(s):
    in_window = set()  # the characters between left and right
    left = 0
    best = 0
    for right in range(len(s)):
        # Shrink from the left until s[right] is no longer inside.
        while s[right] in in_window:
            in_window.remove(s[left])
            left += 1
        in_window.add(s[right])
        best = max(best, right - left + 1)
    return best

Cửa sổ trượt nhảy đến chỉ số xuất hiện lần cuối

Ý tưởng

Bạn đã biết left phải dừng ở đâu: ngay sau vị trí của bản sao xuất hiện trước đó của ký tự mới. Lưu chỉ số cuối cùng của mỗi ký tự trong một map hoặc một mảng có một ô cho mỗi mã ký tự, rồi left nhảy đến đó chỉ trong một bước.

Chỉ nhảy khi chỉ số đó bằng hoặc lớn hơn left. Bản sao cũ hơn đã nằm ngoài cửa sổ, và nhảy đến đó sẽ khiến left lùi lại. Ở mỗi bước, cửa sổ vẫn được tạo theo cách như phiên bản dùng tập hợp, và giờ mỗi ký tự chỉ cần một lần tra cứu, một phép so sánh và một lần ghi.

Thuật toán

Tạo một từ điển rỗng ánh xạ ký tự sang chỉ số cuối cùng, rồi đặt left = 0 và best = 0.
Di chuyển right qua mọi chỉ số và đọc ký tự ch tại đó.
Nếu lần cuối nhìn thấy ch là tại chỉ số bằng hoặc lớn hơn left, đặt left thành chỉ số đó cộng một.
Ghi right làm chỉ số cuối cùng của ch.
Nếu right - left + 1 lớn hơn best, lưu giá trị đó.
Trả về best.

def lengthOfLongestSubstring(s):
    last_seen = {}
    start = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = i
        if i - start + 1 > best:
            best = i - start + 1
    return best

Lỗi thường gặp và trường hợp biên

Lùi left về sau. Trong abba, ký tự a xuất hiện trước ở chỉ số 0 đã nằm ngoài cửa sổ khi bạn gặp ký tự a cuối cùng. Nhảy đến chỉ số 1 đưa ký tự b thứ hai trở lại cửa sổ và cho kết quả 3 thay vì 2.
Tính độ dài cửa sổ bằng right - left. Cả hai đầu đều nằm trong cửa sổ, vì vậy hãy cộng thêm một.
Chuyển chuỗi thành chữ thường trước. a và A là hai ký tự khác nhau ở đây, nên aA có độ dài 2.
Chỉ đo độ dài khi có ký tự lặp lại. Chuỗi không có ký tự lặp lại, chẳng hạn z, sẽ không bao giờ kích hoạt điều kiện này, và kết quả là 0.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán chuỗi con dài nhất không chứa ký tự lặp lại là bao nhiêu?

Cửa sổ trượt chạy trong thời gian O(n), với n là độ dài của chuỗi: cạnh phải đọc mỗi ký tự một lần và cạnh trái chỉ di chuyển về phía trước. Bộ nhớ phụ là O(k), với k là số ký tự khác nhau mà chuỗi có thể chứa, ở đây là 62.

Bạn nên dùng bảng băm hay mảng để lưu các chỉ số cuối cùng?

Cả hai đều có độ phức tạp thời gian O(n). Với một tập hợp ký tự cố định nhỏ như ở đây, dùng mảng có chỉ số là mã ký tự giúp tránh băm và chạy nhanh hơn.

Sự khác nhau giữa chuỗi con và dãy con là gì?

Chuỗi con (substring) là một khối ký tự nằm cạnh nhau, như ode trong coddycode. Dãy con (subsequence) có thể bỏ qua một số ký tự, như cdy. Bài toán này yêu cầu tìm chuỗi con, vì vậy ta có thể dùng một cửa sổ với hai đầu.

def lengthOfLongestSubstring(s):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "coddycode"

Đầu ra mong đợi

Longest Substring Without Repeating Characters

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Kiểm tra từng chuỗi con

Cửa sổ trượt với tập hợp

Cửa sổ trượt nhảy đến chỉ số xuất hiện lần cuối

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự