문제 설명

길이가 n인 문자열 word와 정수 k가 주어지며, k는 n의 약수입니다.

한 번의 연산에서, 임의의 두 인덱스 i와 j를 선택할 수 있습니다(여기서 0 <= i, j < n이고, 두 인덱스 모두 k로 나누어 떨어짐). 그런 다음 j에서 시작하는 길이가 k인 부분 문자열로 i에서 시작하는 길이가 k인 부분 문자열을 대체합니다. 즉, 부분 문자열 word[i…i + k - 1]을 부분 문자열 word[j…j + k - 1]로 바꿉니다.

word를 K-주기 문자열로 만드는 데 필요한 최소 연산 횟수를 반환합니다.

만약 길이가 k인 문자열 s가 존재하여 word가 s를 임의의 횟수 연결한 형태로 표현될 수 있다면, 문자열 word는 K-주기 문자열이라고 합니다. 예를 들어, word == "ababab"라면 word는 s = "ab"일 때 2-주기 문자열입니다.

테스트 케이스

예시 1: 입력: word = "leetcodeleet", k = 4 출력: 1 설명: i = 4와 j = 0을 선택하여 4-주기 문자열을 얻을 수 있습니다. 이 연산 후, word는 "leetleetleet"가 됩니다.

예시 2: 입력: word = "leetcoleet", k = 2 출력: 3 설명: 다음 연산을 수행하여 2-주기 문자열을 얻을 수 있습니다.

해결 방법

문제를 이해하기 위해 먼저 k의 역할을 파악해야 합니다. k는 문자열 길이 n의 약수이므로, 전체 문자열은 겹치지 않는 n//k개의 세그먼트로 나눌 수 있으며, 각 세그먼트의 시작 인덱스는 0, k, 2k, ... 입니다.

우리의 목표는 가능한 적은 연산을 통해 이 k개의 부분 문자열을 모두 동일하게 만드는 것입니다. 따라서 가장 자주 나타나는 부분 문자열을 찾아 전체 문자열의 "주기 문자열"로 사용해야 합니다.

필요한 연산 횟수는 총 세그먼트 수에서 가장 빈번한 부분 문자열의 빈도수를 뺀 값과 같습니다.

코드 구현

Python 구현:

class KPeriodicStringConverter:
    def minOperationsToMakePeriodic(self, text: str, segment_size: int) -> int:
        segment_counts = {}
        total_segments = len(text) // segment_size
        
        # 모든 k-길이 부분 문자열의 빈도를 계산
        for start in range(0, len(text), segment_size):
            current_segment = text[start:start+segment_size]
            segment_counts[current_segment] = segment_counts.get(current_segment, 0) + 1
        
        # 가장 많이 나타나는 부분 문자열의 빈도 찾기
        max_frequency = max(segment_counts.values()) if segment_counts else 0
        
        # 필요한 최소 연산 횟수 계산
        return total_segments - max_frequency

C++ 구현:

class KPeriodicStringConverter {
public:
    int minOperationsToMakePeriodic(const string& text, int segment_size) {
        unordered_map frequency_map;
        int total_segments = text.length() / segment_size;
        int max_frequency = 0;
        
        // 모든 k-길이 부분 문자열의 빈도를 계산
        for (int i = 0; i < text.length(); i += segment_size) {
            string current_segment = text.substr(i, segment_size);
            frequency_map[current_segment]++;
            max_frequency = max(max_frequency, frequency_map[current_segment]);
        }
        
        // 필요한 최소 연산 횟수 반환
        return total_segments - max_frequency;
    }
};