โปรแกรมหาจำนวนกลุ่มสตริงที่เพิ่มหรือลดอย่างต่อเนื่องน้อยที่สุดใน Python

การแบ่งสตริงเป็นกลุ่ม Monotonic น้อยที่สุด

แบ่งสตริง s เป็น substring ที่ต่อเนื่อง น้อยที่สุด โดยแต่ละ substring ต้องเป็น non-decreasing (เพิ่มหรือคงที่) หรือ non-increasing (ลดหรือคงที่) เท่านั้น

อัลกอริทึม

1. ถ้า s ว่าง คืน 0
2. ตัวแปร: last (ตัวอักษรก่อนหน้า), direction (1=เริ่มต้น, 0=เพิ่ม, 2=ลด), count (จำนวนกลุ่ม เริ่ม 1)
3. วนลูปแต่ละตัวอักษร char ใน s
4. ถ้า char > last:
   • ถ้า direction==1 (เริ่มต้น) → direction=0 (เพิ่ม)
   • ถ้า direction==2 (กำลังลด) → เปลี่ยนทิศทาง: direction=1, count+=1
5. ถ้า char < last:
   • ถ้า direction==1 → direction=2 (ลด)
   • ถ้า direction==0 (กำลังเพิ่ม) → เปลี่ยนทิศทาง: direction=1, count+=1
6. อัปเดต last = char
7. คืนค่า count

ตัวอย่างโค้ด

def solve(s):
    if not s:
        return 0
    last = s[0]
    direction = 1
    count = 1
    for char in s:
        if char > last:
            if direction == 1:
                direction = 0
            elif direction == 2:
                direction = 1
                count += 1
        elif char < last:
            if direction == 1:
                direction = 2
            elif direction == 0:
                direction = 1
                count += 1
        last = char
    return count

s = "pqrsrqp"
print(solve(s))

ผลลัพธ์

2

คำอธิบาย

"pqrsrqp" → "pqrs" (non-decreasing) + "rqp" (non-increasing) = 2 กลุ่ม