fork download
copy 
  1. from functools import lru_cache
  2.  
  3. def min_deletions(s: str) -> int:
  4.     n = len(s)
  5.  
  6.     @lru_cache(None)
  7.     def dp(i, j):
  8.         if i > j:
  9.             return 0
  10.         if i == j:
  11.             return 1
  12.  
  13.         res = dp(i + 1, j) + 1
  14.         for k in range(i + 1, j + 1):
  15.             if s[i] == s[k]:
  16.                 res = min(res, dp(i + 1, k - 1) + dp(k, j))
  17.         return res
  18.  
  19.     return dp(0, n - 1)
  20.  
  21.  
  22. # --------- Main stdin/stdout section ---------
  23. if __name__ == "__main__":
  24.     try:
  25.         s = input().strip()
  26.         if s:
  27.             print(min_deletions(s))
  28.         else:
  29.             print(0)
  30.     except Exception as e:
  31.         print(0)
  32.  
Success #stdin #stdout 0.09s 14132KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/okxeJ2
language:
Python 3 (python  3.12)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!