Минимальная сумма квадратов количества символов в данной строке после удаления 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 (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 (c)
где 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