Optimal Partition Of String

Greedy하게 풀면 된다. 소문자만 담을 파티션 하나를 나타내는 집합을 P라고 하자. 문자열을 쭉 훑으면서 P에 이미 해당 알파벳이 있으면 다 초기화하고 새로 시작하면서 개수를 하나 늘리고, 아니면 계속 진행하면 된다.

탐욕적 방법이 동작하는 이유를 증명하면 다음과 같다. 알파벳 a가 P에 있는 상황에서 쭉 훑다가 같은 알파벳 a를 만났다고 하자. 그러면 파티션 개수가 2개가 된다. 그런데 만약 이 탐욕적인 방법이 최소 의 해를 구하는 방법이 아니라면, 이전에 만난 a와 지금 만난 a가 같은 파티션에 속해야 한다. 그래야 파티션 개수가 1개가 되기 때문이다. 하지만 이는 파티션의 정의에 따라 불가능하기 때문에 탐욕적인 방법은 항상 최적의 해를 구할 수 밖에 없다.

def partitionString(s) -> int:
    p = set()
    pn = 1
    for char in s:
        if char not in p:
            p.add(char)
        else:
            p.clear()
            p.add(char)
            pn += 1
    return pn