실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 512 MB |
민혁은 길을 걷다가 길을 잃어버렸다는 생각을 하게 됩니다!
도로를 따라 개의 집()이 줄지어 있습니다. 하지만 집들은 집 번호가 없어서, 민혁이 도로를 따라 그의 위치를 파악하는 것이 어렵습니다. 하지만, 각 집은 도로 옆에 다채로운 우편함을 가지고 있으므로, 민혁은 가장 가까이 있는 우편함의 색을 보고 그가 어디에 있는 지를 정확히 알 수 있을 것이라고 생각합니다.
각 우편함 색은 A..Z 범위의 문자로 지정되므로, 도로를 따라 개의 우편함 순서는 A..Z 범위의 문자를 포함하는 길이 의 문자열로 표현할 수 있습니다. 어떤 우편함은 다른 우편함과 같은 색을 가질 수 있습니다. 민혁은 어떤 값을 보고 도로를 따라 그 순서의 위치를 고유하게 결정할 수 있는 가장 작은 값을 알고 싶어합니다.
예를 들어, 도로를 따라 있는 우편함의 순서가 'ABCDABC'라고 가정합니다. 민혁은 로 설정할 수 없습니다. 왜냐하면 'ABC'를 보았을 때, 연속적인 색상 집합이 있을 수 있는 도로를 따라 두 개의 가능한 위치가 있기 때문입니다. 작동하는 가장 작은 값은 로, 4개의 연속 우편함을 보면 이 색상 순열은 도로를 따라 그의 위치를 고유하게 결정합니다.
입력의 첫 번째 줄에는 이 포함되어 있고, 두 번째 줄에는 각 문자가 범위 A..Z에 포함된 개의 문자를 포함한 문자열이 포함되어 있습니다.
민혁의 문제를 해결하는 가장 작은 값을 지정하는 정수 한 개를 포함하는 줄을 출력합니다.
7 ABCDABC
4
출처: USACO 2019 December Contest, Bronze Problem 2. Where Am I?