K ቁምፊዎችን ካስወገዱ በኋላ በተሰጠው ገመድ ውስጥ የቁምፊዎች ካሬዎች አነስተኛ ድምር


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን
ተራ ሕብረቁምፊ

የችግሩ መግለጫ

ችግሩ “የ 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. ዝቅተኛው እሴት በፍሬክ ድርድር ውስጥ የሚገኙ የእሴቶች ካሬዎች ድምር ነው።

የጊዜ ውስብስብነት = ኦ (n + k * c)
የቦታ ውስብስብነት = ኦ (1)
የት ሐ ቋሚ ሲሆን ይህም በሕብረቁምፊው ውስጥ ካሉ ልዩ ቁምፊዎች ቁጥር ጋር እኩል ይሆናል።

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

ሲ ++ ኮድ

#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. ዝቅተኛው እሴት በቀዳሚ ወረፋ ውስጥ የሚገኙ የእሴቶች ካሬዎች ድምር ነው።

የጊዜ ውስብስብነት = ኦ (n + k * ምዝግብ ማስታወሻ (ሐ))
የቦታ ውስብስብነት = ኦ (ሐ)
የት ሐ ቋሚ ሲሆን ይህም በሕብረቁምፊው ውስጥ ካሉ ልዩ ቁምፊዎች ቁጥር ጋር እኩል ይሆናል። እኛ ቅድሚያ ከሚሰጡት ወረፋዎች ኬ ንጥረ ነገሮችን ስለምናስወግድ ፡፡ ቅድሚያ ከሚሰጣቸው ወረፋዎች ማስገባት እና ማስወገድ ኦ (log 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

ሲ ++ ኮድ

#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