Cho chuỗi s. Chuỗi con "nice" nếu mọi chữ cái xuất hiện trong nó đều có cả chữ hoa và chữ thường. Tìm chuỗi con nice dài nhất, nếu nhiều thì lấy xuất hiện sớm nhất.
Ví dụ: s = "ZbybBbz" → "bBb" (chứa 'b' và 'B').
Thuật toán giải quyết (Vét cạn O(n^2))
- cur_max := -1, res := "".
- Với mỗi i từ 0 đến n-1:
- Khởi tạo set upper, lower.
- Thêm s[i] vào upper/lower tương ứng.
- Với j từ i+1 đến n-1:
- Cập nhật upper/lower với s[j].
- Nếu upper == lower: nếu j-i > cur_max: cập nhật cur_max, res = s[i:j+1].
- Trả về res.
Ví dụ triển khai
def solve(s):
cur_max = -1
res = ""
for i in range(len(s)):
c = s[i]
upper = set()
lower = set()
if c.islower():
lower.add(c)
if c.isupper():
upper.add(c.lower())
for j in range(i+1, len(s)):
c = s[j]
if c.islower():
lower.add(c)
if c.isupper():
upper.add(c.lower())
if upper == lower:
if j - i > cur_max:
cur_max = j - i
res = s[i:j+1]
return res
s = "ZbybBbz"
print(solve(s))Đầu vào
"ZbybBbz"
Đầu ra
bBb