สมมติว่าเรามีสตริง s เราต้องหา substring ที่ nice ที่สุดและยาวที่สุด สตริง s จะเป็น nice เมื่อสำหรับทุกตัวอักษรใน s ตัวอักษรนั้นปรากฏทั้งพิมพ์ใหญ่และพิมพ์เล็ก ถ้ามีหลายอัน ให้คืน substring ที่ปรากฏก่อนสุด
เช่น s = "ZbybBbz" ผลลัพธ์คือ "bBb" เพราะมีทั้ง 'b' และ 'B'
ขั้นตอนการแก้ปัญหา
- cur_max = -1, res = ""
- วนลูป i จาก 0 ถึง len(s)-1:
- c = s[i], upper = set(), lower = set()
- ถ้า c เป็นพิมพ์เล็ก: lower.add(c)
- ถ้า c เป็นพิมพ์ใหญ่: upper.add(c.lower())
- วนลูป j จาก i+1 ถึง len(s)-1:
- c = s[j]
- ถ้า c พิมพ์เล็ก: lower.add(c)
- ถ้า c พิมพ์ใหญ่: upper.add(c.lower())
- ถ้า upper == lower:
- ถ้า j-i > cur_max: cur_max = j-i, res = s[i:j+1]
- คืน res
ตัวอย่างโค้ด
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))
ข้อมูลเข้า
"ZbybBbz"
ข้อมูลออก
bBb
