หาสตริงระหว่างสองสตริงในลำดับเล็กซิโคกราฟิก Python

ภาพรวม

โจทย์หาสตริงที่มีความยาวเท่ากัน อยู่ระหว่าง S และ T ในลำดับเล็กซิโคกราฟิก (lexicographic order) คืน -1 ถ้าไม่มี

ตัวอย่าง

S = "bbb", T = "ddd"

สตริงถัดไปจาก "bbb" คือ "bbc" (บวก 1 ตัวท้าย) → "bbc" < "ddd" ✓ → คืน "bbc"

อัลกอริทึม: หาสตริงถัดไป (Next String)

1. เริ่มจากตัวท้าย (rightmost)
2. ถ้าไม่ใช่ 'z' → เพิ่ม 1 (a→b, b→c, ..., y→z) คืนผลลัพธ์
3. ถ้าเป็น 'z' → เปลี่ยนเป็น 'a' แล้วไปตัวก่อนหน้า (carry)

โค้ด Python

def find_next(string):
    n = len(string)
    for i in range(n - 1, -1, -1):
        if string[i] != 'z':
            k = ord(string[i])
            string[i] = chr(k + 1)
            return "".join(string)
        string[i] = 'a'
    return None  # ถ้าทั้งหมดเป็น z

S = "bbb"
T = "ddd"
S = list(S)
res = find_next(S)
if res != T:
    print(res)
else:
    print(-1)

หมายเหตุ

• ทำงานกับ list of chars เพื่อแก้ไข in-place
• ถ้า next string = T → ไม่มีสตริงระหว่าง → -1
• เวลา O(n) สำหรับความยาวสตริง

ผลลัพธ์

bbc