First Unique Character in a String

Q: Độ phức tạp thời gian của bài toán ký tự đầu tiên không trùng lặp trong chuỗi là bao nhiêu?

Đếm các chữ cái rồi quét chuỗi là hai lượt, mỗi lượt gồm n bước, nên độ phức tạp thời gian là O(n) . 26 bộ đếm chiếm cùng một lượng bộ nhớ với mọi độ dài, nên bộ nhớ bổ sung là O(1) .

DễBăm

+10

Bạn nhận được một chuỗi s gồm các chữ cái tiếng Anh viết thường. Hãy tìm ký tự đầu tiên chỉ xuất hiện đúng một lần trong toàn bộ chuỗi và trả về chỉ số của ký tự đó, tính từ 0. Nếu mọi ký tự đều xuất hiện nhiều hơn một lần, hãy trả về -1.

Hàm

firstUniqChar(s: string) → integer

sstring: chuỗi cần tìm, chỉ dùng chữ thường
Trả vềinteger: chỉ số của chữ cái đầu tiên chỉ xuất hiện đúng một lần, hoặc -1 nếu không có chữ cái nào như vậy

Ràng buộc

1 ≤ s.length ≤ 5 × 10⁴
s chỉ chứa các chữ cái tiếng Anh viết thường (a đến z).

Ví dụ

Đầu vào: s = "coddycode"
Đầu ra: 4
Giải thích: Trong coddycode, c và o xuất hiện hai lần, còn d xuất hiện ba lần. Cả y (chỉ số 4) và e (chỉ số 8) đều xuất hiện một lần, và y đứng trước, nên đáp án là 4.

Đầu vào: s = "swiss"
Đầu ra: 1
Giải thích: Ký tự s xuất hiện ba lần. Cả w ở chỉ số 1 và i ở chỉ số 2 đều xuất hiện một lần, và w đứng trước.

Đầu vào: s = "aabbcc"
Đầu ra: -1
Giải thích: Mỗi chữ cái trong aabbcc xuất hiện hai lần, nên đáp án là -1.

Câu hỏi mở rộng

Các ký tự lần lượt xuất hiện từ một luồng. Sau mỗi ký tự, bạn sẽ báo cáo ký tự duy nhất đầu tiên tính đến thời điểm đó như thế nào?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Một chữ cái trông có vẻ duy nhất khi bạn gặp nó có thể lặp lại ở cuối chuỗi, vì vậy chỉ nhìn lướt từ trái sang phải một lần là chưa đủ. Trước tiên, hãy đếm từng chữ cái, sau đó lượt duyệt thứ hai có thể xác định trong thời gian hằng số liệu mỗi vị trí có chứa một chữ cái duy nhất hay không.

Tìm bản sao thứ hai của từng chữ cái

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

Ý tưởng

Với mỗi vị trí từ trái sang, hãy quét toàn bộ chuỗi để tìm một vị trí khác có cùng chữ cái. Quét cả hai phía: một bản sao ở trước cũng khiến chữ cái không hợp lệ như một bản sao ở sau. Vị trí đầu tiên không có bản sao là đáp án. Trong coddycode, các vị trí từ 0 đến 3 đều tìm thấy bản sao, còn y ở chỉ số 4 thì không.

Dừng ở bản sao đầu tiên cũng không giúp ích gì khi mỗi chữ cái nằm trong một đoạn dài, chẳng hạn 2000 a, rồi đến 2000 b và cứ thế tiếp tục: mỗi lần quét đều đi qua tất cả các đoạn trước đó. Với n = 5 × 10^4, số phép so sánh vượt quá một tỷ.

Thuật toán

Với mỗi chỉ số i từ trái sang phải:
Duyệt qua mọi chỉ số j khác i, rồi dừng ở chỉ số đầu tiên mà s[j] bằng s[i].
Nếu không có j nào như vậy, hãy trả về i.
Nếu mọi chỉ số đều tìm thấy một bản sao, hãy trả về -1.

def firstUniqChar(s):
    n = len(s)
    for i in range(n):
        repeated = False
        for j in range(n):  # look for another copy of s[i]
            if j != i and s[j] == s[i]:
                repeated = True
                break
        if not repeated:
            return i
    return -1

Đếm chữ cái, rồi quét

Ý tưởng

Đếm mỗi chữ cái một lần thay vì tìm kiếm lại ở từng vị trí. Chỉ có 26 chữ cái, vì vậy 26 bộ đếm có thể lưu mọi số đếm, với chỉ số được tính bằng mã của chữ cái trừ mã của a.

Lượt duyệt đầu tiên điền các bộ đếm; với coddycode, chỉ có y và e kết thúc với số đếm là 1. Lượt duyệt thứ hai đi qua chuỗi từ trái sang phải và dừng ở chữ cái đầu tiên có số đếm là 1, chữ y ở chỉ số 4. Hai lượt duyệt, mỗi lượt gồm n bước, có độ phức tạp thời gian O(n), còn 26 bộ đếm có độ phức tạp không gian O(1) với mọi độ dài.

Thuật toán

Tạo một mảng gồm 26 số 0.
Với mỗi chữ cái trong s, tăng bộ đếm tương ứng lên 1.
Duyệt lại s từ chỉ số 0. Trả về chỉ số đầu tiên có chữ cái với số đếm bằng 1.
Nếu duyệt hết, trả về -1.

def firstUniqChar(s):
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for i, ch in enumerate(s):
        if counts[ord(ch) - ord("a")] == 1:
            return i
    return -1

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

Chỉ kiểm tra các chữ cái trước vị trí i. Trong abca, chữ a đầu tiên không có chữ nào giống nó đứng trước, nhưng nó không phải là chữ cái duy nhất.
Duyệt mảng bộ đếm thay vì chuỗi ở lượt thứ hai. Với ba, bộ đếm đầu tiên bằng 1 thuộc về a, nhưng đáp án là chỉ số 0.
Dùng mã ký tự thô để đánh chỉ số cho các bộ đếm. a có mã 97, vượt xa vị trí cuối của 26 bộ đếm.
Trả về chữ cái thay vì chỉ số của nó, hoặc trả về chỉ số bắt đầu từ 1 trong Lua hoặc R.

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

Độ phức tạp thời gian của bài toán ký tự đầu tiên không trùng lặp trong chuỗi là bao nhiêu?

Đếm các chữ cái rồi quét chuỗi là hai lượt, mỗi lượt gồm n bước, nên độ phức tạp thời gian là O(n). 26 bộ đếm chiếm cùng một lượng bộ nhớ với mọi độ dài, nên bộ nhớ bổ sung là O(1).

Bạn có thể giải bài này chỉ bằng một lượt duyệt chuỗi không?

Có. Trong một lượt duyệt, hãy lưu chỉ số xuất hiện lần đầu của mỗi chữ cái, hoặc đánh dấu là bị lặp khi chữ cái đó xuất hiện lần nữa. Sau đó, lấy chỉ số nhỏ nhất trong số 26 chữ cái chỉ xuất hiện một lần. Chuỗi được đọc một lần, và bước kiểm tra cuối cùng tốn 26 bước.

Bạn nên dùng bản đồ băm hay mảng để đếm các chữ cái?

Chỉ với các chữ cái viết thường, mảng gồm 26 bộ đếm sẽ nhỏ hơn và nhanh hơn. Từ điển băm là lựa chọn phù hợp khi chuỗi có thể chứa bất kỳ ký tự nào, chẳng hạn như văn bản Unicode. Thuật toán vẫn như cũ: đếm, rồi quét chuỗi.

def firstUniqChar(s):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "coddycode"

Đầu ra mong đợi