โปรแกรมแบ่งสตริงเป็นสตริงย่อยไม่ซ้ำสูงสุดใน Python

ปัญหา

สตริง s แบ่งเป็นสตริงย่อยไม่ซ้ำกันมากที่สุด (concatenation ต้องได้ s เดิม)

ตัวอย่าง

s="pqpqrrr" → 5 (แบ่งเป็น ['p','q','pq','r','rr'])

ขั้นตอนการแก้ปัญหา

1. res := [0]
2. DFS: dfs(s, path=set()):
   • ถ้า s ว่าง: res[0] = max(res[0], len(path))
   • วน i 1..len(s):
     • x := s[:i]
     • ถ้า x not in path: dfs(s[i:], path | {x})
3. คืน res[0]

การนำไปใช้งาน (Python)

def solve(s):
    res = [0]
    def dfs(s, path=set()):
        if not s:
            res[0] = max(res[0], len(path))
            return
        for i in range(1, len(s) + 1):
            x = s[:i]
            if x not in path:
                dfs(s[i:], path | {x})
    dfs(s)
    return res[0]

s = "pqpqrrr"
print(solve(s))

อินพุต

"pqpqrrr"

เอาต์พุต

5