ผลรวมขั้นต่ำของกำลังสองของจำนวนอักขระในสตริงที่กำหนดหลังจากลบอักขระ 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. ค่าต่ำสุดคือผลรวมของกำลังสองของค่าที่มีอยู่ในอาร์เรย์ความถี่

ความซับซ้อนของเวลา = 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 เป็นค่าคงที่ซึ่งเท่ากับจำนวนอักขระที่ไม่ซ้ำกันในสตริง เนื่องจากเรากำลังลบองค์ประกอบ k ออกจากคิวลำดับความสำคัญ การแทรกและการลบออกจากคิวลำดับความสำคัญ O (บันทึก N) เวลา. และด้วยเหตุนี้จึงเกิดปัจจัย logN ความซับซ้อนของพื้นที่เป็นเพราะเราสร้างอาร์เรย์ความถี่ แต่เนื่องจากขนาดของอาร์เรย์ความถี่ไม่ขึ้นอยู่กับอินพุต ดังนั้นความซับซ้อนของอวกาศจึงคงที่

รหัสเพื่อค้นหาผลรวมขั้นต่ำของกำลังสองของจำนวนอักขระในสตริงที่กำหนดหลังจากลบอักขระ k

รหัส Java

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