k အက္ခရာများဖယ်ရှားပြီးနောက်ပေးထားသော string ကိုအတွက်ဇာတ်ကောင်များ၏စတုရန်းအနည်းဆုံးပေါင်းလဒ်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ
ဆံပင်ကြိုး ကြိုး

ပြProbleနာဖော်ပြချက်

“ k အက္ခရာများဖယ်ရှားပြီးနောက်ဇာတ်ကောင်၏အနည်းဆုံးစတုရန်းအရေအတွက်အနည်းဆုံးကိန်းဂဏန်းအရေအတွက်သည်” ပြproblemနာကသင့်အားပေးထားသည်ဟုဖော်ပြသည် ကြိုး သာစာလုံးအသေးများပါဝင်သည်။ ကျန်ရှိသော string တွင်စာလုံးတစ်ခုချင်းစီ၏ကြိမ်နှုန်း၏နှစ်ထပ်ကိန်းအနိမ့်ဆုံးဖြစ်သော string ကိုမှ k အက္ခရာများကိုဖယ်ရှားခွင့်ပြုသည်။ နိမ့်ဆုံးတန်ဖိုးကိုရှာ။ ပုံနှိပ်ပါ။

ဥပမာ

str = "aabcd"
k = 2
3

 

str = "aabbcc"
k = 2
6

 

k အက္ခရာများဖယ်ရှားပြီးနောက်ပေးထားသော string ကိုအတွက်ဇာတ်ကောင်များ၏စတုရန်းအနည်းဆုံးပေါင်းလဒ်

str = "aaaaabbxd"
k = 1
22

နုံချဉ်းကပ်နည်း

ဖယ်ရှားပစ်ရန်အမြဲတမ်းအကောင်းဆုံးဖြစ်သည် ဇာတ်ကောင် အများဆုံးကြိမ်နှုန်းနှင့်အတူ။

  1. ပေးထားသောမူရင်း string တွင်စာလုံးများ၏ကြိမ်နှုန်းကိုရေတွက်။ freq ခင်းကျင်းပါ။
  2. စီ နိုင်ရန်အတွက်လျော့ကျအတွက် freq ခင်းကျင်း။
  3. အဆင့် ၄ 'k' ကြိမ်ကိုလုပ်ပါ။
  4. freq ခင်းကျင်းစာရင်းရှိပထမဆုံး element ၏ကြိမ်နှုန်းကို 1 သို့လျှော့ချပြီး freq ခင်းကျင်းမှုကိုပြန်လည်စီပါ။
  5. နိမ့်ဆုံးတန်ဖိုးဆိုသည်မှာ Freq ခင်းကျင်းပြထားသောတန်ဖိုးများ၏နှစ်ထပ်ကိန်းများဖြစ်သည်။

အချိန်ရှုပ်ထွေး = အို (n + k * c)
အာကာသရှုပ်ထွေးမှု = အို (၁)
c သည်စဉ်ဆက်မပြတ်ဖြစ်သောကြောင့် string အတွင်းရှိထူးခြားသောစာလုံးအရေအတွက်နှင့်တူညီသည်။

k အက္ခရာများဖယ်ရှားပြီးနောက်ပေးထားသော string ကိုအတွက်အက္ခရာအရေအတွက်၏အနိမ့်ဆုံးပေါင်းလဒ်ကိုရှာဖွေကုဒ်

ဂျာဗားကုဒ်

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. တစ်ဦး Create ဦး စားပေးတန်းစီ အများဆုံးအမှိုက်ပုံဖြစ်သောက q ။
  2. မူရင်း string တွင်စာလုံးအားလုံး၏ကြိမ်နှုန်းကိုရေတွက်ပြီး၎င်းတို့ကို ဦး စားပေးတန်းစီပါ။
  3. အဆင့် ၄ 'k' ကြိမ်ကိုလုပ်ပါ။
  4. ဦး စားပေးတန်းစီ၏ထိပ်ကိုဖယ်ရှားပါ၊ ၁ ကိုလျှော့ချပါ။ အကယ်၍ သုညမဟုတ်ပါက၎င်းကို ဦး စားပေးတန်းစီသို့ပြန်ပို့ပါ။
  5. အနိမ့်ဆုံးတန်ဖိုးဆိုသည်မှာ ဦး စားပေးတန်းစီတွင်ရှိနေသောတန်ဖိုးများ၏နှစ်ထပ်ကိန်းဖြစ်သည်။

အချိန်ရှုပ်ထွေး = အို (n + k * မှတ်တမ်း (ဂ))
အာကာသရှုပ်ထွေးမှု = အို (ဂ)
c သည်စဉ်ဆက်မပြတ်ဖြစ်သောကြောင့် string အတွင်းရှိထူးခြားသောစာလုံးအရေအတွက်နှင့်တူညီသည်။ ကျနော်တို့ ဦး စားပေးတန်းစီကနေ elements element တွေကိုဖယ်ရှားပစ်နေကြသည်ကတည်းက။ ဦး စားပေးတန်းစီကနေသွင်းခြင်းနှင့်ဖယ်ရှားခြင်း အို (မှတ်တမ်း N) အချိန်။ ဒါကြောင့် logN အချက်တစ်ခုရောက်လာတယ်။ အာကာသတွင်းရှုပ်ထွေးမှုသည်ကျွန်ုပ်တို့သည် frequency array ကိုဖန်တီးခဲ့ကြသောကြောင့်ဖြစ်သည်။ frequency array ၏အရွယ်အစားသည် input မှမသက်ဆိုင်သောကြောင့်ဖြစ်သည်။ ထို့ကြောင့်ရှုပ်ထွေးမှုသည်အမြဲတမ်းတည်ရှိသည်။

k အက္ခရာများဖယ်ရှားပြီးနောက်ပေးထားသော string ကိုအတွက်အက္ခရာအရေအတွက်၏အနိမ့်ဆုံးပေါင်းလဒ်ကိုရှာဖွေကုဒ်

ဂျာဗားကုဒ်

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