Символдар квадраттарының минималды қосындысы k таңбаларды жойғаннан кейін берілген жолда есептеледі


Күрделілік дәрежесі орта
Жиі кіреді Amazon
кезек String

Проблемалық мәлімдеме

«K таңбаларын алып тастағаннан кейін берілген жолдағы таңбалар квадраттарының минималды қосындысы» есебінде сізге берілгені айтылады жол тек кіші әріптерден тұрады. Жолдан k таңбаларын алып тастауға рұқсат етіледі, қалған жолда әр таңбаның жиілік квадраттарының қосындысы минималды болады. Осы минималды мәнді тауып, оны басып шығарыңыз.

мысалдары

str = "aabcd"
k = 2
3

 

str = "aabbcc"
k = 2
6

 

Символдар квадраттарының минималды қосындысы k таңбаларды жойғаннан кейін берілген жолда есептеледі

str = "aaaaabbxd"
k = 1
22

Аңғал көзқарас

Әрдайым оңтайлы болып табылады кейіпкер максималды жиілікпен.

  1. Берілген түпнұсқа жолда барлық таңбалардың жиілігін санап, оны жиіліктер массивінде сақтаңыз.
  2. сорт азайту ретіндегі жиілік жиымы.
  3. 4-қадамды 'k' рет қайталаңыз.
  4. Жиілік жиымындағы бірінші элементтің жиілігін 1-ге азайтып, жиілік жиымын қайтадан сұрыптаңыз.
  5. Минималды мән - жиілік жиымында берілген мәндер квадраттарының қосындысы.

Уақыттың күрделілігі = O (n + k * c)
Ғарыштың күрделілігі = O (1)
мұндағы c тұрақты, ол жолдағы бірегей таңбалардың санына тең.

K таңбаларын жойғаннан кейін берілген жолдағы таңбалар санының минималды квадраттарының қосындысын табуға арналған код

Java коды

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

Оңтайлы тәсіл

Таңбаны максималды жиілікпен жою мақсатына басымдылық кезегі арқылы оңтайлы қол жеткізуге болады.

  1. а жасау Басым кезек q, бұл ең үлкен үйінді.
  2. Түпнұсқа жолда барлық таңбалардың жиілігін санап, олардың кезегіне басымдық беріңіз.
  3. 4-қадамды 'k' рет қайталаңыз.
  4. Басым кезектің жоғарғы бөлігін алып тастаңыз, оны 1-ге азайтыңыз және егер ол нөлге тең болмаса, оны кезекке қойыңыз.
  5. Минималды мән - бұл басымдылық кезегінде тұрған мәндер квадраттарының қосындысы.

Уақыттың күрделілігі = O (n + k * log (c))
Ғарыштың күрделілігі = O (c)
мұндағы c тұрақты, ол жолдағы бірегей таңбалардың санына тең. Біз k элементтерін басымдылық кезегінен алып тастағандықтан. Енгізу және кезектен бас тарту O (журнал N) уақыт. Осылайша logN факторы келді. Кеңістіктің күрделілігі мынада, өйткені біз жиілік жиымын құрдық, бірақ жиілік жиымының мөлшері кіріске тәуелді емес. Сонымен, ғарыштың күрделілігі тұрақты.

K таңбаларын жойғаннан кейін берілген жолдағы таңбалар санының минималды квадраттарының қосындысын табуға арналған код

Java коды

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