k 문자를 제거한 후 주어진 문자열에서 문자 수의 최소 제곱합

난이도 중급
자주 묻는 질문 아마존
조회수 41

문제 정책

“k 문자를 제거한 후 주어진 문자열에서 문자 수의 최소 제곱합”문제는 소문자 만 포함. 나머지 문자열에서 각 문자의 빈도 제곱의 합이 최소가되도록 문자열에서 k 문자를 제거 할 수 있습니다. 그 최소값을 찾아서 인쇄하십시오.

str = "aabcd"
k = 2
3

 

str = "aabbcc"
k = 2
6

 

k 문자를 제거한 후 주어진 문자열에서 문자 수의 최소 제곱합

str = "aaaaabbxd"
k = 1
22

순진한 접근

제거하는 것이 항상 최적입니다. 문자 최대 주파수로.

  1. 주어진 원래 문자열에서 모든 문자의 빈도를 세고 freq 배열에 저장하십시오.
  2. 종류 내림차순의 freq 배열.
  3. 4 단계를 'k'번 반복합니다.
  4. freq 배열에서 첫 번째 요소의 주파수를 1만큼 줄이고 freq 배열을 다시 정렬합니다.
  5. 최소값은 freq 배열에있는 값의 제곱의 합입니다.

시간 복잡성 = O (n + k * c)
공간 복잡성 = O (1)
여기서 c는 문자열의 고유 문자 수와 같은 상수입니다.

k 문자를 제거한 후 주어진 문자열에서 문자 수의 최소 제곱합을 찾는 코드

자바 코드

import java.util.Arrays;
import java.util.Collections;
class MinimumSumOfSquaresOfCharacterCountsInAGivenStringAfterRemovingKCharacters {
    private static int minSumSquares(String str, int k) {
        char sArr[] = str.toCharArray();
        int minSum = 0;

        // create a freq array, with initial value as 0
        Integer freq[] = new Integer[26];
        for (int i = 0; i < 26; i++) {
            freq[i] = 0;
        }

        // traverse in the original string and calculate the frequency of every character
        for (int i = 0; i < sArr.length; i++) {
            freq[sArr[i] - 'a']++;
        }

        // sort the array in descending order
        Arrays.sort(freq, Collections.reverseOrder());

        // remove k characters
        for (int i = 0; i < k; i++) {
            // remove the character with maximum freq and reduce the freq
            freq[0]--;
            // sort the array in descending order
            Arrays.sort(freq, Collections.reverseOrder());
        }

        // minSum is the sum of squares of all the elements in freq array
        for (int i = 0; i < 26; i++) {
            minSum += (freq[i] * freq[i]);
        }

        return minSum;
    }

    public static void main(String[] args) {
        // Example 1
        String str1 = "aabcd";
        int k1 = 2;
        System.out.println(minSumSquares(str1, k1));

        // Example 2
        String str2 = "aabbcc";
        int k2 = 2;
        System.out.println(minSumSquares(str2, k2));

        // Example 3
        String str3 = "aaaaabbxd";
        int k3 = 1;
        System.out.println(minSumSquares(str3, k3));
    }
}
3
6
22

C ++ 코드

#include<bits/stdc++.h> 
using namespace std; 

int minSumSquares(string str, int k) {
    int minSum = 0;
    
    // create a freq array, with initial value as 0
    int freq[26];
    for (int i = 0; i < 26; i++) {
        freq[i] = 0;
    }
    
    // traverse in the original string and calculate the frequency of every character
    for (int i = 0; i < str.length(); i++) {
        freq[str[i] - 'a']++;
    }
    
    // sort the array in descending order
    sort(freq, freq + 26, greater<int>());
    
    // remove k characters
    for (int i = 0; i < k; i++) {
        // remove the character with maximum freq and reduce the freq
        freq[0]--;
        // sort the array in descending order
        sort(freq, freq + 26, greater<int>());
    }
    
    // minSum is the sum of squares of all the elements in freq array
    for (int i = 0; i < 26; i++) {
        minSum += (freq[i] * freq[i]);
    }
    
    return minSum;
}

int main() {
    // Example 1
    string str1 = "aabcd";
    int k1 = 2;
    cout<<minSumSquares(str1, k1)<<endl;

    // Example 2
    string str2 = "aabbcc";
    int k2 = 2;
    cout<<minSumSquares(str2, k2)<<endl;

    // Example 3
    string str3 = "aaaaabbxd";
    int k3 = 1;
    cout<<minSumSquares(str3, k3)<<endl;
    
    return 0;
}
3
6
22

최적의 접근 방식

최대 빈도로 캐릭터를 제거하는 목표는 Priority Queue를 사용하여 최적으로 달성 할 수 있습니다.

  1. 만들기 우선 순위 대기열 q는 최대 힙입니다.
  2. 원래 문자열에서 모든 문자의 빈도를 세고 우선 순위 대기열을 만듭니다.
  3. 4 단계를 'k'번 반복합니다.
  4. 우선 순위 대기열의 맨 위를 제거하고 1만큼 줄이고 XNUMX이 아니면 우선 순위 대기열로 다시 밀어 넣습니다.
  5. 최소값은 우선 순위 대기열에있는 값의 제곱의 합입니다.

시간 복잡성 = O (n + k * log (c))
공간 복잡성 = O (c)
여기서 c는 문자열의 고유 문자 수와 같은 상수입니다. 우선 순위 대기열에서 k 요소를 제거하고 있기 때문입니다. 우선 순위 대기열에서 삽입 및 제거 O (로그 N) 시각. 그래서 인자 logN이 왔습니다. 공간 복잡성은 주파수 배열을 만들었지 만 주파수 배열의 크기가 입력과 무관하기 때문입니다. 따라서 공간 복잡성은 일정합니다.

k 문자를 제거한 후 주어진 문자열에서 문자 수의 최소 제곱합을 찾는 코드

자바 코드

import java.util.Collections;
import java.util.PriorityQueue;

class MinimumSumOfSquaresOfCharacterCountsInAGivenStringAfterRemovingKCharacters {
    private static int minSumSquares(String str, int k) {
        char[] sArr = str.toCharArray();
        // create a frequency array
        int freq[] = new int[26];

        // traverse in the original string and count the frequency of each character
        for (int i = 0; i < sArr.length; i++) {
            freq[sArr[i] - 'a']++;
        }

        // create a priority queue and store the frequency of each character
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < 26; i++) {
            if (freq[i] != 0)
                priorityQueue.add(freq[i]);
        }

        // remove k characters
        for (int i = 0; i < k; i++) {
            // remove the character with maximum frequency
            int curr = priorityQueue.poll();
            // reduce the frequency
            curr--;
            if (curr != 0)
                priorityQueue.add(curr);
        }

        int minSum = 0;

        // min sum is the sum of squares of elements in priority queue
        for (Integer i : priorityQueue) {
            minSum += (i * i);
        }

        return minSum;
    }

    public static void main(String[] args) {
        // Example 1
        String str1 = "aabcd";
        int k1 = 2;
        System.out.println(minSumSquares(str1, k1));

        // Example 2
        String str2 = "aabbcc";
        int k2 = 2;
        System.out.println(minSumSquares(str2, k2));

        // Example 3
        String str3 = "aaaaabbxd";
        int k3 = 1;
        System.out.println(minSumSquares(str3, k3));
    }
}
3
6
22

C ++ 코드

#include<bits/stdc++.h> 
using namespace std; 

int minSumSquares(string str, int k) {
    int minSum = 0;
    
    // create a freq array, with initial value as 0
    int freq[26];
    for (int i = 0; i < 26; i++) {
        freq[i] = 0;
    }
    
    // traverse in the original string and calculate the frequency of every character
    for (int i = 0; i < str.length(); i++) {
        freq[str[i] - 'a']++;
    }
    
    // create a priority queue and store the frequency of each character
    priority_queue<int> pq;
    for (int i = 0; i < 26; i++) {
        if (freq[i] != 0) {
            pq.push(freq[i]);
        }
    }
    
    // remove k characters
    for (int i = 0; i < k; i++) {
        // remove the character with maximum frequency
        int curr = pq.top();
        pq.pop();
        // reduce the frequency
        curr--;
        if (curr != 0) {
            pq.push(curr);
        }
    }
    
    // min sum is the sum of squares of elements in priority queue
    while (!pq.empty()) {
        minSum += (pq.top() * pq.top());
        pq.pop();
    }
    
    return minSum;
}

int main() {
    // Example 1
    string str1 = "aabcd";
    int k1 = 2;
    cout<<minSumSquares(str1, k1)<<endl;

    // Example 2
    string str2 = "aabbcc";
    int k2 = 2;
    cout<<minSumSquares(str2, k2)<<endl;

    // Example 3
    string str3 = "aaaaabbxd";
    int k3 = 1;
    cout<<minSumSquares(str3, k3)<<endl;
    
    return 0;
}
3
6
22
Translate »