Problem:


String Compression

Problem

アルファベットの小文字と数字からなる文字列 S が与えられる。次の手順で文字列 S の長さを圧縮する。

文字列内の文字の順番を任意の順番に入れ替える。

例: "0ig3he12fz99" &rarr; "efghiz012399"

次の操作を任意の回数行う。

文字列内にある、"abcdefghijklmnopqrstuvwxyz"の連続した部分文字列を選び、(先頭の文字)'-'(末尾の文字)に置き換える。

例: "efghiz012399" &rarr; "e-iz012399"

文字列内にある、公差が1であるような数字列("0123456789"の連続した部分文字列)を選び、(先頭の数字)'-'(末尾の数字)に置き換える。

例: "e-iz012399" &rarr; "e-iz0-399"

文字列 S を圧縮して得られる文字列の長さの最小値を求めよ。

Input

文字列 S が１行で与えられる。

Constraints

1 ≤ |S| ≤ 100

文字列Sはアルファベットの小文字と数字のみを含む

Output

文字列 S を圧縮して得られる文字列の長さの最小値を1行に出力せよ。圧縮できない場合は元の文字列 S の長さを出力せよ。

Sample Input 1

0ig3he12fz99

Sample Output 1

9

Sample Input 2

1122334455

Sample Output 2

6



Sample input:
0ig3he12fz99


Sample output:
9

Submission status: Wrong Answer

Solution code:
s = list(input())
s.sort()
i = 0
while i + 3 < len(s):
    if ord(s[i]) + 3 == ord(s[i + 1]) + 2 == ord(s[i + 2]) + 1 == ord(s[i + 3]):s.pop(i)
    else:i += 1
print(len(s))

Submission status: Wrong Answer

Solution code:
s = list(input())
s.sort()
i = 0
while True:
    if chr(ord(s[i]) + 1) in s and chr(ord(s[i]) + 2) in s:
        s.append("-")
        s.remove(chr(ord(s[i]) + 1))
        j = 2
        while True:
            if chr(ord(s[i]) + j + 1) in s:
                s.remove(chr(ord(s[i]) + j))
                j += 1
            else:break
    i += 1
    if i >= len(s) or s[i] == "-":
        break
print(len(s))

Submission status: Accepted

Solution code:
# AOJ 1564: String Compression
# Python3 2018.7.13 bal4u

f = [0]*128
ch0, ch9n, cha, chzn = ord('0'), ord('9')+1, ord('a'), ord('z')+1

def act(start, end, n):
	while True:
		for i in range(start, end):
			if f[i] == 0: continue
			f[i] -= 1; S.append(i)
			n -= 1
			if n <= 0: return

S = list(input())
w = len(S)
for s in S: f[ord(s)] += 1
n1 = sum(f[ch0:ch9n]); n2 = w-n1
S = []
if n1 > 0: act(ch0, ch9n, n1)
if n2 > 0: act(cha, chzn, n2)
ans, i = w, 0
while i < w:
	j = i+1
	while j < w and S[j] == S[j-1]+1: j += 1
	if j-i > 3: ans -= j-i-3
	i = j
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from collections import defaultdict

S = input()
S = sorted(S)
S = list(map(ord, S))

ans = 0
while len(S) > 0:
    mn = S[0]
    S.remove(mn)
    nxt = mn + 1
    succ = 1
    while True:
        if nxt in S:
            S.remove(nxt)
            succ += 1
            nxt += 1
        else:
            break
    ans += min(3, succ)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#C
s = list(input())
abc = list("-abcdefghijklmnopqrstuvwxyz-")
num = list("-0123456789-")
abc_cnt = [0]*28
num_cnt = [0]*12

for i in range(len(s)):
    for j in range(1,27):
        if s[i] == abc[j]:
            abc_cnt[j] += 1

for i in range(len(s)):
    for j in range(1,11):
        if s[i] == num[j]:
            num_cnt[j] += 1
ans = 0
abc_sum = sum(abc_cnt)
num_sum = sum(num_cnt)


while abc_sum > 0:
    start = 100
    current = 1
    while current < 27:
        if abc_cnt[current-1] == 0 and abc_cnt[current] > 0:
            start = min(start,current)

        if abc_cnt[current+1] == 0 and abc_cnt[current] > 0:
            ans += min(3, current - start + 1)
            abc_cnt[current] -= 1
            abc_sum -= 1
            break

        if abc_cnt[current] > 0:
            abc_cnt[current] -= 1
            abc_sum -= 1

        current += 1

while num_sum > 0:
    start = 100
    current = 1
    while current < 11:
        if num_cnt[current-1] == 0 and num_cnt[current] > 0:
            start = min(start,current)

        if num_cnt[current+1] == 0 and num_cnt[current] > 0:
            ans += min(3, current - start + 1)
            num_cnt[current] -= 1
            num_sum -= 1
            break

        if num_cnt[current] > 0:
            num_cnt[current] -= 1
            num_sum -= 1

        current += 1


print(ans)