K حروف کو ہٹانے کے بعد دیئے گئے اسٹرنگ میں کردار کے گنبد کے مربعوں کی کم از کم رقم


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون
قطار سلک

مسئلہ یہ بیان

مسئلہ "K حروف کو ہٹانے کے بعد کسی خاص سٹرنگ میں کرداروں کے مربعوں کی کم سے کم رقم کا اضافہ" یہ بتاتا ہے کہ آپ کو a سٹرنگ صرف چھوٹے حرفوں پر مشتمل. آپ کو k حروف کو اسٹرنگ سے ہٹانے کی اجازت ہے جیسے کہ باقی سٹرنگ میں ہر کردار کی فریکوئنسی کے مربع کا مجموعہ کم سے کم ہے۔ کم سے کم قیمت معلوم کریں اور اسے پرنٹ کریں۔

مثال کے طور پر

str = "aabcd"
k = 2
3

 

str = "aabbcc"
k = 2
6

 

K حروف کو ہٹانے کے بعد دیئے گئے اسٹرنگ میں کردار کے گنبد کے مربعوں کی کم از کم رقم

str = "aaaaabbxd"
k = 1
22

بولی اپروچ

اس کو دور کرنا ہمیشہ ہی بہتر ہے کردار زیادہ سے زیادہ تعدد کے ساتھ.

  1. دیئے گئے اصل تار میں ، تمام حروف کی تعدد گنیں اور اسے فریق صف میں محفوظ کریں۔
  2. ترتیب گھٹا ہوا ترتیب میں freq سرنی.
  3. مرحلہ 4 'کے' اوقات دہرائیں۔
  4. فریک صف میں پہلے عنصر کی تعدد کو 1 سے کم کریں اور فریک صف کو دوبارہ ترتیب دیں۔
  5. کم سے کم قیمت فریق صف میں موجود اقدار کے مربعوں کا مجموعہ ہے۔

وقت کی پیچیدگی = O (n + k * c)
خلائی پیچیدگی = O (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

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 'کے' اوقات دہرائیں۔
  4. ترجیحی قطار کے اوپری حصے کو ہٹا دیں ، اسے 1 سے کم کریں اور اگر یہ صفر نہیں ہے تو اسے ترجیحی قطار پر واپس دھکیلیں۔
  5. کم از کم قیمت ترجیحی قطار میں موجود اقدار کے مربعوں کا مجموعہ ہے۔

وقت کی پیچیدگی = O (n + k * لاگ (c))
خلائی پیچیدگی = O (c)
جہاں سی مستقل رہتا ہے جو تار کے انوکھا حروف کی تعداد کے برابر ہوتا ہے۔ چونکہ ہم k عناصر کو ترجیحی قطار سے ہٹا رہے ہیں۔ ترجیحی قطار سے اندراج اور ہٹانا O (لاگ ن) وقت اور اس طرح ایک عنصر لاگ این آیا۔ اسپیس کی پیچیدگی اس وجہ سے ہے کہ ہم نے فریکوینسی سرنی تشکیل دی ہے لیکن چونکہ فریکونسی سرنی کا سائز ان پٹ سے آزاد ہے۔ اور اس طرح جگہ کی پیچیدگی مستقل ہے۔

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

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