Longest Palindrome

Q: Độ phức tạp thời gian của chuỗi đối xứng dài nhất là bao nhiêu?

Độ phức tạp thời gian O(n) khi đếm: mỗi chữ cái cộng 1 vào một bộ đếm, và việc cộng các cặp lại đọc 128 bộ đếm, bất kể độ dài của s . Độ phức tạp không gian là O(1) . Sắp xếp và ghép các phần tử liền kề tốn thời gian O(n log n) và không gian O(n) .

DễBăm Tham lam

+10

Bạn nhận được một chuỗi s gồm các chữ cái viết hoa và viết thường. Hãy sắp xếp lại các chữ cái để tạo thành chuỗi đối xứng dài nhất có thể, rồi trả về độ dài của chuỗi đó. Bạn có thể sắp xếp các chữ cái theo bất kỳ thứ tự nào và bỏ qua một số chữ cái, nhưng chỉ được dùng mỗi chữ cái tối đa bằng số lần chữ cái đó xuất hiện trong s.

Chữ cái viết hoa và viết thường là các chữ cái khác nhau, nên Aa không phải là chuỗi đối xứng.

Hàm

longestPalindrome(s: string) → integer

sstring: các chữ cái bạn có thể dùng, cả chữ hoa lẫn chữ thường
Trả vềinteger: độ dài của chuỗi đối xứng dài nhất bạn có thể tạo từ những chữ cái đó

Ràng buộc

1 ≤ s.length ≤ 5 × 10⁴
s chỉ chứa các chữ cái tiếng Anh, từ a đến z và từ A đến Z.
Bạn không cần dùng mọi chữ cái.

Ví dụ

Đầu vào: s = "coddyCode"
Đầu ra: 5
Giải thích: o xuất hiện hai lần và d xuất hiện ba lần, các chữ cái còn lại xuất hiện một lần. Một cặp chữ o, một cặp chữ d và một chữ cái còn lại ở giữa tạo thành độ dài 5, ví dụ như doCod.

Đầu vào: s = "Aa"
Đầu ra: 1
Giải thích: A và a là hai chữ cái khác nhau, nên không có cặp nào tồn tại. Một chữ cái đứng riêng là một chuỗi đối xứng có độ dài 1.

Đầu vào: s = "xxxyyy"
Đầu ra: 5
Giải thích: Hai ký tự x và hai ký tự y tạo thành từng cặp, còn một ký tự thừa nằm ở giữa, như trong xyxyx. Ký tự y cuối cùng không có cặp nên nằm ngoài.

Câu hỏi mở rộng

Bạn có thể trả về một chuỗi đối xứng dài nhất cùng với độ dài của nó, vẫn trong O(n) thời gian không?

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

Vì bạn có thể sắp xếp lại, thứ tự của s không quan trọng, chỉ cần quan tâm mỗi chữ cái xuất hiện bao nhiêu lần. Trong một chuỗi đối xứng (palindrome), mỗi chữ cái đều có một chữ cái tương ứng ở phía bên kia, ngoại trừ nhiều nhất một chữ cái ở giữa. Vì vậy, hãy đếm các chữ cái, giữ lại từng cặp và thêm một chữ cái ở giữa nếu còn dư chữ nào.

Sắp xếp và ghép các phần tử liền kề

Ý tưởng

Sắp xếp các chữ cái giống nhau cạnh nhau, để mỗi cặp nằm sát nhau. Trong xxxyyy, các chữ x ở vị trí 0 và 1 giống nhau: lấy cặp đó rồi di chuyển hai vị trí. Ở chỉ số 2, x và y khác nhau, nên chữ x đó không ghép được thành cặp và bạn di chuyển một vị trí. Các chữ y ở vị trí 3 và 4 tạo thành cặp thứ hai, còn chữ y cuối cùng đứng một mình. Hai cặp cho kết quả 4, cộng thêm một chữ cái ở giữa: 5.

Một chữ cái còn dư chính xác khi các cặp đã dùng ít hơn tổng số n chữ cái, nên bạn không cần cờ riêng. Việc sắp xếp tốn thời gian O(n log n) và bản sao đã sắp xếp chiếm O(n) dung lượng.

Thuật toán

Sắp xếp các chữ cái trong s.
Duyệt qua các chữ cái đã sắp xếp bằng chỉ số i. Nếu các chữ cái ở i và i+1 giống nhau, hãy cộng 2 vào độ dài rồi di chuyển hai vị trí; nếu không, di chuyển một vị trí.
Nếu độ dài nhỏ hơn số chữ cái, hãy cộng 1 cho chữ cái ở giữa.
Trả về độ dài.

def longestPalindrome(s):
    letters = sorted(s)
    n = len(letters)
    length = 0
    i = 0
    while i + 1 < n:
        if letters[i] == letters[i + 1]:
            length += 2  # a pair: one copy on each side of the middle
            i += 2
        else:
            i += 1
    # A letter left without a partner can stand alone in the middle
    if length < n:
        length += 1
    return length

Đếm từng chữ cái

Ý tưởng

Đếm cho ta cùng thông tin mà không cần sắp xếp. Dùng một bộ đếm cho mỗi mã ký tự, tổng cộng 128 bộ đếm, để A và a được tính vào các bộ đếm khác nhau. Một chữ cái xuất hiện c lần tạo thành số chữ cái chẵn lớn nhất không vượt quá c.

Với coddyCode, các cặp chữ cái o và d tạo thành 4 chữ cái. Còn lại 5 chữ cái không ghép cặp, và chữ nào trong số đó cũng có thể đứng ở giữa: 5. Chữ cái thứ hai không ghép cặp sẽ không có chữ cái đối xứng với nó.

Duyệt s một lần để điền các bộ đếm, rồi duyệt 128 bộ đếm một lần để cộng số cặp: thời gian O(n) và bộ nhớ phụ O(1) (O(n) trong R, vì trước tiên R chuyển s thành một vector mã ký tự).

Thuật toán

Tạo 128 bộ đếm có giá trị 0, rồi tăng bộ đếm tương ứng với mỗi chữ cái trong s lên 1.
Với mỗi bộ đếm, cộng số đếm sau khi làm tròn xuống thành số chẵn vào độ dài.
Nếu độ dài nhỏ hơn độ dài của s, thì có một số bộ đếm là số lẻ, vì vậy hãy cộng 1 cho chữ cái ở giữa.
Trả về độ dài.

def longestPalindrome(s):
    counts = [0] * 128  # one counter per character code, so 'A' and 'a' differ
    for ch in s:
        counts[ord(ch)] += 1
    length = 0
    for count in counts:
        length += count // 2 * 2  # every pair fits, one copy on each side
    # Fewer letters used than s has: some count is odd, so one letter can go in the middle
    if length < len(s):
        length += 1
    return length

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

Bỏ hoàn toàn các số lượng lẻ. Một chữ cái xuất hiện 3 lần vẫn tạo thành một cặp: xxxyyy cho kết quả 5, không phải 1.
Cộng thêm 1 cho mỗi số lượng lẻ. Chỉ có thể có một chữ cái ở giữa, nên xxxyyy cho kết quả 5, không phải 6.
Coi A và a là cùng một chữ cái. Aa không có cặp nào, nên đáp án là 1, không phải 2.
Chỉ định kích thước bộ đếm cho các chữ cái từ a đến z. Chữ cái viết hoa có mã từ 65 đến 90 và nằm ngoài phạm vi đó; hãy dùng toàn bộ mã ký tự làm chỉ số.

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

Chuỗi đối xứng dài nhất khác gì với chuỗi con đối xứng dài nhất?

Ở đây, bạn có thể sắp xếp lại các chữ cái, nên chỉ cần quan tâm đến số lượng và việc đếm sẽ giải quyết bài toán trong O(n). Longest Palindromic Substring yêu cầu tìm một chuỗi đối xứng đã xuất hiện dưới dạng một khối gồm các chữ cái liên tiếp, nên cần một phương pháp khác, chẳng hạn như mở rộng quanh từng tâm. Với abab, bài toán này cho kết quả 4 (abba), còn phiên bản chuỗi con cho kết quả 3 (aba).

Độ phức tạp thời gian của chuỗi đối xứng dài nhất là bao nhiêu?

Độ phức tạp thời gian O(n) khi đếm: mỗi chữ cái cộng 1 vào một bộ đếm, và việc cộng các cặp lại đọc 128 bộ đếm, bất kể độ dài của s. Độ phức tạp không gian là O(1). Sắp xếp và ghép các phần tử liền kề tốn thời gian O(n log n) và không gian O(n).

Bạn có phải dùng mọi ký tự của s không?

Không. Mỗi cặp đều được đưa vào, và ở giữa có thể có nhiều nhất một chữ cái không ghép cặp. Vì vậy, đáp án là độ dài của s khi có nhiều nhất một chữ cái xuất hiện số lần lẻ; nếu không, đáp án là độ dài của s trừ đi số chữ cái xuất hiện số lần lẻ, rồi cộng 1.

def longestPalindrome(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