結果

問題 No.52 よくある文字列の問題
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:16:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 40 ms / 5,000 ms
コード長 920 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 53,916 KB
最終ジャッジ日時 2025-03-20 21:17:30
合計ジャッジ時間 1,198 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

S = input().strip()
n = len(S)

# Initialize DP table where dp[l][r] is a set of possible strings
dp = [[set() for _ in range(n)] for _ in range(n)]

# Base case: single character substrings
for i in range(n):
    dp[i][i].add(S[i])

# Fill DP table for substrings of length 2 to n
for length in range(2, n + 1):
    for l in range(n - length + 1):
        r = l + length - 1
        # Take left character and append all possible strings from substring (l+1, r)
        left_set = dp[l + 1][r]
        temp_left = {S[l] + s for s in left_set} if left_set else set()
        # Take right character and append all possible strings from substring (l, r-1)
        right_set = dp[l][r - 1]
        temp_right = {S[r] + s for s in right_set} if right_set else set()
        # Combine both possibilities
        dp[l][r] = temp_left.union(temp_right)

# The answer is the size of the set at dp[0][n-1]
print(len(dp[0][n - 1]))
0