סכום מינימלי של ריבועי ספירת תווים במחרוזת נתונה לאחר הסרת תווי k


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית
תור מחרוזת

הצהרת בעיה

הבעיה "סכום מינימלי של ריבועי תווים סופרת במחרוזת נתונה לאחר הסרת תווי k" קובעת כי ניתנת לך מחרוזת המכיל תווים קטנים בלבד. מותר להסיר תווים 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.

מורכבות זמן = O (n + k * c)
מורכבות בחלל = O (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

גישה אופטימלית

המטרה של הסרת הדמות בתדירות מרבית יכולה להיות מושגת בצורה אופטימלית באמצעות תור עדיפות.

  1. צור תור עדיפות q, שהוא ערימה מקסימלית.
  2. במחרוזת המקורית, ספור את התדירות של כל הדמויות ועשה עליהן תור עדיפות.
  3. חזור על שלב 4 'k' פעמים.
  4. הסר את החלק העליון של תור העדיפות, צמצם אותו ב -1 ואם הוא לא אפס דחף אותו חזרה לתור העדיפות.
  5. הערך המינימלי הוא סכום ריבועי הערכים הקיימים בתור העדיפות.

מורכבות זמן = O (n + k * יומן (c))
מורכבות בחלל = O (c)
כאשר c קבוע שהוא שווה למספר התווים הייחודיים במחרוזת. מכיוון שאנו מסירים אלמנטים k מתור העדיפות. הכנסה והסרה מתור עדיפות O (יומן 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

קוד 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