ڪي اکرن کي گهٽائڻ کان پوءِ گهٽ ڏنل تعداد ۾ ڪردارن جي گهٽ ۾ گهٽ تعداد


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon
پنگتي حيثيت رکي ٿو اسٽرنگ

مسئلي جو بيان

مسئلو ”ڪي اکرن کي گهٽائڻ جي گهٽ تعداد هڪ ڏنل اسٽرنگ ۾ شمار ٿيل اکرن کي ڪٽڻ کان پوءِ ڳڻتي آهي ته“ توهان کي هڪ ڏني وئي آهي جملو صرف هيٺين اکرن تي مشتمل هوندو. توهان کي ڪي اسٽرنگ مان ڪي حذف ڪرڻ جي اجازت آهي ته باقي واري تار ۾ هر حرف جي تعدد جو تعداد گهٽ ۾ گهٽ آهي. گهٽ ۾ گهٽ قيمت ڳوليو ۽ ان کي پرنٽ ڪيو.

مثال

str = "aabcd"
k = 2
3

 

str = "aabbcc"
k = 2
6

 

ڪي اکرن کي گهٽائڻ کان پوءِ گهٽ ڏنل تعداد ۾ ڪردارن جي گهٽ ۾ گهٽ تعداد

str = "aaaaabbxd"
k = 1
22

نائي اچڻ وارو

اهو هميشه بهتر طور تي ختم ڪرڻ بهتر آهي شخصيت وڌ کان وڌ فریکوئنسي سان.

  1. ڏنل اصل تار ۾ ، سڀني اکرن جي فريڪوئنسي ڳڻيو ۽ ان کي فريق صف ۾ محفوظ ڪريو.
  2. جي حساب سان گهٽجڻ جي حڪم ۾ فريڪ صف.
  3. ٻيهر قدم 4 'k' وار.
  4. 1 پاران فري برٽ صف ۾ پھريائين عنصر جي تعدد گھٽايو ۽ فريق صف کي وري ترتيب ڏيو.
  5. گهٽ ۾ گهٽ قدر فريق صف ۾ موجود قدرن جي مجموعن جو مجموعو آهي.

وقت جي پيچيدگي = اي (ن + ڪي * سي)
خلائي پيچيدگي = اي (1)
جتي سي مسلسل آهي جيڪو تار ۾ منفرد اکرن جي تعداد جي برابر آهي.

ڪي اکرن کي گهٽائڻ کانپوءِ ڪٽر جي تعداد جي گهٽ ۾ گهٽ تعداد ڳوليو ويو

جاوا ڪوڊ

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

ڪوشان وارو رستو

وڌ کان وڌ فریکوئنسي سان ڪردار کي ڪ ofڻ جو مقصد ترجيحي قطار سان استعمال ڪري بهتر نموني حاصل ڪري سگھجي ٿو.

  1. هڪ ٺاهيو ترجيحات جي قطار ق ، جيڪا وڌ کان وڌ شيشي آهي.
  2. اصلي تار ۾ ، سڀني اکرن جي فريڪوئنسي ڳڻيو ۽ انهن جي هڪ ترجيحي قطار ٺاهيو.
  3. ٻيهر قدم 4 'k' وار.
  4. ترجيحي قطار جي چوٽي کي هٽايو ، ان کي 1 ذريعي گھٽايو ۽ جيڪڏهن صفر نه آهي ته ان کي ترجيحي قطار ڏانهن واپس ڇڪيو وڃي.
  5. گھٽ ۾ گھٽ قيمت ترجيحن جي قطار ۾ موجود قدرن جي مجموعن جو مجموعو آھي.

وقت جي پيچيدگي = اي (ن + ڪي * لاگ (سي))
خلائي پيچيدگي = اي (سي)
جتي سي مسلسل آهي جيڪو تار ۾ منفرد اکرن جي تعداد جي برابر آهي. جتان اسان ترجيحن جي قطار مان ڪي عناصر کي ڪ areي رهيا آهيون. ترجيحاتي قطار تان هٽائڻ ۽ ختم ڪرڻ اي (لاگ اين) وقت. ۽ اهڙيء طرح هڪ عنصر لاگ اين آيو. خلائي پيچيدگي سبب آهي ڇو ته اسان هڪ فریکوئنسي ليئر ٺاهيو آهي پر جڏهن کان فریکوئنسي صف جي ماپ ان پٽ کان آزاد آهي. ۽ اهڙي طرح خلائي پيچيدگي مستقل آهي.

ڪي اکرن کي گهٽائڻ کانپوءِ ڪٽر جي تعداد جي گهٽ ۾ گهٽ تعداد ڳوليو ويو

جاوا ڪوڊ

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