문자열의 아름다움

알고리즘
$unpretty$
$Lump$

from collections import defaultdict
from itertools import groupby
def solution(s):
    lumps = defaultdict(lambda: defaultdict(int))
    for char, group in groupby(s):
        lumps[char][len(list(group))] += 1
    unpretty = ((n := len(s)) - 1) * n * (n + 1) // 6
    for lump in lumps.values():
        total = sum(l * count for l, count in lump.items())
        both_side = sum(lump.values())
        for i in range(1, max(lump) + 1):
            unpretty -= total * (total - 1) // 2
            total -= both_side
            both_side -= lump[i]
    return unpretty

알고리즘

lump(s) : s양끝의 알파벳이 같은 덩어리의 크기

lump(s) = 1 + lump(s[1:-1]) if s[0] == s[-1] else 0

unpretty(s) : s가 모두다른 알파벳으로 이루어져있다고 가정했을 때의 아름다움 길이

unpretty(s) = len(s) - 1

s = aaabcdefaa 이면 lump(s) = 2, unpretty(s) = 9

pretty(s) = unpretty(s) - lump(s)

pretty(zzabcdzz) = 7 - 2

pretty(zzzabz) = 5 - 1

$\sum pretty(s_{sub}) = \sum unpretty(s_{sub}) - \sum Lump(s_{sub})$

$unpretty$

문자열 s가 모두 다른 알파벳으로 구성되어있다고 가정했을 때의, 최대 아름다움 길이다. s의 모든 부분 문자열들의 $unpretty$ 값을 구해준 뒤, 덩어리들의 갯수들만 빼주면 된다.

unpretty = (n-1) * n * (n+1) / 6

$Lump$

모든 부분문자열들의 $unpretty$ 길이들의 합을 구했으니, 모든 부분문자열들의 $Lump$ 합을 구해서 빼주면된다.

임의의 한 부분문자열을 보자.

문자의 양끝이 달라질때까지 양끝의 알파벳을 빼주고 1씩 더해가면 lump가 나오게된다. 그렇다면 모든 부분문자열에대해서 계산을 해야하는데

문자열 s 내에서 알파벳a의 분포가 이렇게 되있을 때

aaaa__aaa_____a__aa__aaa

lump[a] = {4 : 1,
           3 : 2,
           2 : 1,
           1 : 1}

양끝이 a로 이루어진 부분문자열의 경우의 수는

$total = 4 \cdot 1 + 3 \cdot 2 + 2 \cdot 1 + 1 \cdot 1$

$_{total}C _{2}$

그 다음 양끝의 a를 없애고난 뒤의 total은 각 덩어리들에서 1을 빼주고 다시 조합을 구해주면된다.

$total = (4-1) \cdot 1 + (3-1) \cdot 2 + (2-1) \cdot 1 + (1-1) \cdot 1$

$_{total}C _{2}$

이 계산을 s를 구성하는 모든 알파벳에대해 다 해주면 된다.

from collections import defaultdict
from itertools import groupby
def solution(s):
    lumps = defaultdict(lambda: defaultdict(int))
    for char, group in groupby(s):
        lumps[char][len(list(group))] += 1
    unpretty = ((n := len(s)) - 1) * n * (n + 1) // 6
    for lump in lumps.values():
        total = sum(l * count for l, count in lump.items()) # 전체 알파벳의 개수
        both_side = sum(lump.values()) # 양쪽끝 알파벳이 같은 경우의 수
        for i in range(1, max(lump) + 1):
            unpretty -= total * (total - 1) // 2
            total -= both_side # 양끝의 알파벳 하나씩 뺌
            both_side -= lump[i] # 양끝의 알파벳 경우의수 최신화
    return unpretty

문자열의 아름다움

알고리즘

$unpretty$

$Lump$

Comments