의 개수와 의 개수를 각각 이라고 하자.
만약 또는 이면 문자열은 처음부터 단색이므로 답은 이다.
만약 이면 문자열 전체를 한 번에 삭제할 수 있으므로 답은 이다.
이제 이고 두 문자가 모두 존재한다고 하자. 더 많이 등장하는 문자를 majority 문자라고 부르자. majority 문자를 , 나머지 문자를 로 바꾼 배열을 라고 하자. 전체 합을 라고 하면 이다.
삭제할 수 있는 부분 문자열은 정확히 합이 인 구간이다. 따라서 어떤 연산을 여러 번 하더라도 전체 합 는 변하지 않는다. 마지막 문자열은 단색이어야 하므로, 마지막에는 majority 문자만 정확히 개 남아야 한다.
즉, 문제는 다음과 같이 바뀐다.
majority 문자 중 일부를 남기고, 나머지 문자들을 합이 인 연속 구간들로 나누어 삭제한다. 이때 삭제하는 구간의 개수를 최소화한다.
prefix sum을 다음과 같이 정의하자.
구간 의 합이 이라는 것은 이라는 뜻이다.
를 앞의 글자까지 처리했고, 번째 위치가 현재 경계일 때 필요한 최소 연산 횟수라고 하자. 위치 의 문자가 majority 문자라면 이 문자를 남길 수 있다. 이때 이전 경계 에서 까지의 구간을 삭제하려면 여야 한다.
같은 prefix sum을 가진 이전 경계들의 최솟값을 에 저장하면 각 위치마다 에 전이할 수 있다.
전이는 다음 두 경우이다.
모든 위치를 처리한 뒤, 마지막 suffix도 합이 이면 한 번 더 삭제할 수 있다.
전체 시간 복잡도는 , 메모리 복잡도는 이다.
