Python - หาซับสตริงเพิ่มขึ้นติดกันยาวที่สุดขึ้นต้นด้วย 'a' พร้อม wildcard '?'

โจทย์: กำหนดสตริงพิมพ์เล็ก s ประกอบด้วยตัวอักษรและสัญลักษณ์ '?' แต่ละ '?' สามารถลบหรือแทนที่ด้วยตัวอักษรพิมพ์เล็กได้ ต้องการหาความยาวของซับสตริงที่เพิ่มขึ้นติดกัน (Consecutive Increasing) ยาวที่สุดที่ ขึ้นต้นด้วย 'a'

ตัวอย่าง

Input: s = "vta???defke"
Output: 6
เหตุผล: แทน '?' เป็น 'b','c','d' ได้ "vtabcdefke" ซับสตริง "abcdef" ยาว 6 ตัว เริ่มด้วย 'a' และเพิ่มขึ้นติดกัน

อัลกอริทึม: Single Pass Greedy

ใช้ตัวแปรติดตามสถานะปัจจุบัน: length (ความยาวลำดับปัจจุบัน), qmarks (จำนวน '?' สะสม), maxlen (คำตอบ)

ขั้นตอนการทำงาน

1. วนอ่านตัวอักษร c ใน s
2. หาก c == '?': เพิ่ม qmarks
3. หากเป็นตัวอักษร:
   • คำนวณ idx = ord(c) - ord('a') (0=a, 1=b, ..., 25=z)
   • อัปเดต length:
     • หาก length <= idx <= length + qmarks → ขยายลำดับได้: length = idx + 1
     • หาก idx <= qmarks → เริ่มลำดับใหม่จาก 'a' ผ่าน '?': length = idx + 1
     • อื่นๆ → รีเซ็ต: length = 0
   • รีเซ็ต qmarks = 0
   • อัปเดต maxlen = max(maxlen, min(length + qmarks, 26)) (สูงสุด 26 ตัวอักษร)

โค้ด Python

def solve(s):
    maxlen = length = qmarks = 0
    
    for c in s:
        if c == "?":
            qmarks += 1
        else:
            idx = ord(c) - ord("a")
            # ตรวจสอบว่าตัวอักษรนี้ต่อยอดลำดับได้หรือไม่
            if length <= idx <= length + qmarks or idx <= qmarks:
                length = idx + 1
            else:
                length = 0
            qmarks = 0
        maxlen = max(maxlen, min(length + qmarks, 26))
    
    return maxlen

# ทดสอบ
s = "vta???defke"
print(solve(s))  # Output: 6

การทำงานทีละขั้นตอน (Trace)

s = "v t a ? ? ? d e f k e"

ความซับซ้อน

• Time Complexity: O(n) - ผ่านสตริง 1 รอบ
• Space Complexity: O(1) - ตัวแปรคงที่

ข้อสังเกตสำคัญ

• ลำดับต้องเริ่มด้วย 'a' (idx=0) เสมอ
• '?' ใช้เป็น "ตัวเติม" ได้ แต่ต้องต่อเนื่อง
• ความยาวสูงสุดคือ 26 (a-z)
• เงื่อนไข idx <= qmarks จัดการกรณีเริ่มใหม่จาก 'a' ผ่าน '?' (เช่น "???c" → "abc")