Տրված տողի նիշերի քառակուսիների նվազագույն գումարը k նիշերը հեռացնելուց հետո


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon
Հերթ String

Խնդիրի հայտարարություն

«Կ նիշերը հեռացնելուց հետո տրված տողի մեջ նիշերի քանակի նվազագույն քառակուսիների գումարը» խնդիրը ասում է, որ ձեզ տրված է լարային պարունակող միայն փոքրատառ նիշեր, Ձեզ թույլատրվում է տողից հեռացնել 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 զանգվածում առկա արժեքների քառակուսիների գումարն է:

Timeամանակի բարդություն = O (n + k * c)
Տիեզերական բարդություն = Ո (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

Օպտիմալ մոտեցում

Նիշը առավելագույն հաճախականությամբ հեռացնելու նպատակը կարող է օպտիմալ կերպով հասնել Priority Queue- ի միջոցով:

  1. Ստեղծել Գերակայության հերթ q, որը առավելագույն կույտ է:
  2. Սկզբնական տողի մեջ հաշվիր բոլոր նիշերի հաճախականությունը և դրանցից կազմիր առաջնային հերթ:
  3. Կրկնեք քայլը 4 'k' անգամ:
  4. Հեռացրեք գերակայության հերթի վերին մասը, 1-ով կրճատեք այն և եթե այն զրո չէ, այն հետ մղեք դեպի առաջնահերթ հերթ:
  5. Նվազագույն արժեքը առաջնահերթության հերթում առկա արժեքների քառակուսիների գումարն է:

Timeամանակի բարդություն = O (n + k * տեղեկամատյան (c))
Տիեզերական բարդություն = Ո (գ)
որտեղ c հաստատուն է, ինչը հավասար է լարի եզակի նիշերի թվին: Քանի որ մենք վերացնում ենք k տարրերը առաջնային հերթից: Տեղադրում և հեռացում առաջնահերթ հերթերից O (տեղեկամատյան N) ժամանակը Եվ այդպիսով եկավ գործոնի գրանցումը: Տիեզերական բարդությունն այն պատճառով է, որ մենք ստեղծեցինք հաճախականության զանգված, բայց քանի որ հաճախականության զանգվածի չափը անկախ է մուտքից: Եվ այդպիսով տիեզերական բարդությունը մշտական ​​է:

Կոդ `նիշերի քառակուսիների նվազագույն գումարը գտնելու համար տվյալ տողի մեջ 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