ปัญหา
กำหนดสตริง s ประกอบด้วยตัวอักษร "x", "y", "z" ต้องการหาจำนวน subsequences ที่มี i ตัว 'x' ตามด้วย j ตัว 'y' ตามด้วย k ตัว 'z' โดยที่ i, j, k ≥ 1
ตัวอย่าง: s = "xxyz" → ผลลัพธ์ 3 เพราะมี subsequences "xyz" (2 แบบ เลือก x ตัวไหนก็ได้) และ "xxyz" (1 แบบ)
อัลกอริทึม Dynamic Programming แบบ Optimized
ใช้ตัวแปร 3 ตัวนับจำนวน subsequences ที่สร้างได้จนถึงตำแหน่งปัจจุบัน:
x: จำนวน subsequences ที่เป็น "x..." (เริ่มต้นด้วย x อย่างน้อย 1 ตัว)y: จำนวน subsequences ที่เป็น "x...y..." (มี x แล้วตามด้วย y อย่างน้อย 1 ตัว)z: จำนวน subsequences ที่เป็น "x...y...z..." (ครบทั้ง 3 กลุ่ม)
วนลูปแต่ละตัวอักษรใน s:
- ถ้าเป็น 'x':
x = x * 2 + 1(ยืด subsequences เก่า + เริ่ม subsequence ใหม่) - ถ้าเป็น 'y':
y = y * 2 + x(ยืด subsequences เก่า + ต่อ y เข้ากับ x subsequences) - ถ้าเป็น 'z':
z = z * 2 + y(ยืด subsequences เก่า + ต่อ z เข้ากับ y subsequences)
คำตอบสุดท้ายคือค่า z
การนำไปใช้ Python
class Solution:
def solve(self, s):
n = len(s)
x = 0
y = 0
z = 0
for i in range(n):
if s[i] == "x":
x *= 2
x += 1
if s[i] == "y":
y *= 2
y += x
if s[i] == "z":
z *= 2
z += y
return z
ob = Solution()
print(ob.solve("xxyz")) # 3
อธิบายตัวอย่าง "xxyz"
- 'x': x=1
- 'x': x=1*2+1=3 (subsequences: x₁, x₂, x₁x₂)
- 'y': y=0*2+3=3 (ต่อ y: x₁y, x₂y, x₁x₂y)
- 'z': z=0*2+3=3 (ต่อ z: x₁yz, x₂yz, x₁x₂yz)
ผลลัพธ์ 3 subsequences: "xyz" (2 แบบ), "xxyz" (1 แบบ)
ความซับซ้อน
- Time: O(n) - วนลูปผ่านสตริง 1 ครั้ง
- Space: O(1) - ใช้ตัวแปรคงที่ 3 ตัว
