fork download
copy 
  1. def solve(S):
  2.     N = len(S)
  3.     # Initialize dp array with infinity
  4.     dp = [float('inf')] * (N + 1)
  5.     dp[0] = 0  # 0 components requires 0 length string
  6.  
  7.     # Dictionary to store the lengths of shortest strings for each number of components
  8.     for length in range(1, N + 1):
  9.         for start in range(N - length + 1):
  10.             substring = S[start:start + length]
  11.             last_index = start
  12.             components = 1  # Start with one component
  13.  
  14.             # Create bridges based on the substring
  15.             for j in range(1, length):
  16.                 current_index = start + j
  17.                 # If the current character matches the previous one in the substring
  18.                 if S[last_index] == S[current_index]:
  19.                     continue
  20.                 else:
  21.                     components += 1
  22.  
  23.                 last_index = current_index
  24.  
  25.             # Update the dp array
  26.             dp[components] = min(dp[components], length)
  27.  
  28.     # Prepare the result array
  29.     result = []
  30.     for k in range(1, N + 1):
  31.         result.append(dp[k] if dp[k] != float('inf') else 0)
  32.  
  33.     return result
  34.  
  35. def main():
  36.     import sys
  37.     input = sys.stdin.read
  38.     S = input().strip()
  39.  
  40.     result = solve(S)
  41.     print(" ".join(map(str, result)))
  42.  
  43. if __name__ == "__main__":
  44.     main()
Success #stdin #stdout 0.04s 9720KB
comments (?)
stdin
copy 
aabcabcaa
stdout
copy 
1 2 3 4 5 6 7 0 0
https://ideone.com/PaL3B1
language:
Python 3 (python  3.9.5)
created:
5 days 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!