ផលបូកអប្បបរមានៃការ៉េនៃចំនួនតួអក្សរនៅក្នុងខ្សែអក្សរដែលបានផ្តល់បន្ទាប់ពីដកតួអក្សរ k


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon
ជួរ ខ្សែអក្សរ

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ ចំនួនអប្បបរមានៃការេនៃតួអក្សររាប់នៅក្នុងខ្សែអក្សរដែលបានផ្តល់បន្ទាប់ពីដកតួអក្សរ k” ចែងថាអ្នកត្រូវបានផ្តល់ឱ្យ ខ្សែអក្សរ មានតែអក្សរតូចប៉ុណ្ណោះ។ អ្នកត្រូវបានអនុញ្ញាតឱ្យដកតួអក្សរ k ចេញពីខ្សែអក្សរដូចជានៅក្នុងខ្សែអក្សរដែលនៅសល់ចំនួនសរុបនៃការ៉េនៃប្រេកង់នៃតួអក្សរនីមួយៗមានអប្បបរមា។ រកតម្លៃអប្បបរមានោះហើយបោះពុម្ពវា។

ឧទាហរណ៍

str = "aabcd"
k = 2
3

 

str = "aabbcc"
k = 2
6

 

ផលបូកអប្បបរមានៃការ៉េនៃចំនួនតួអក្សរនៅក្នុងខ្សែអក្សរដែលបានផ្តល់បន្ទាប់ពីដកតួអក្សរ k

str = "aaaaabbxd"
k = 1
22

វិធីសាស្ត្រណាតូស

វាល្អប្រសើរបំផុតក្នុងការយកឯកសារ តួអក្សរ ជាមួយប្រេកង់អតិបរមា។

  1. នៅក្នុងខ្សែអក្សរដើមដែលបានផ្តល់ឱ្យ, រាប់ប្រេកង់នៃតួអក្សរទាំងអស់ហើយរក្សាទុកវានៅក្នុងអារេហ្វ្រី។
  2. តម្រៀប អារេ freq នៅក្នុងលំដាប់ថយចុះ។
  3. ធ្វើជំហានទី ៤ 'k' ម្តងទៀត។
  4. កាត់បន្ថយភាពញឹកញាប់នៃធាតុទីមួយនៅក្នុងអារេ freq ដោយ 1 និងតម្រៀបអារេ freq ម្តងទៀត។
  5. តម្លៃអប្បបរមាគឺជាផលបូកនៃការ៉េនៃតម្លៃដែលមាននៅក្នុងអារេហ្វ្រី។

ស្មុគស្មាញពេលវេលា = O (n + k * គ)
ភាពស្មុគស្មាញនៃលំហ = ឱ (១)
ដែលគគឺថេរដែលស្មើនឹងចំនួនតួអក្សរពិសេសនៅក្នុងខ្សែអក្សរ។

លេខកូដដើម្បីស្វែងរកចំនួនអប្បបរមានៃការ៉េនៃចំនួនតួអក្សរនៅក្នុងខ្សែអក្សរដែលបានផ្តល់បន្ទាប់ពីដកតួអក្សរ 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. ធ្វើជំហានទី ៤ 'k' ម្តងទៀត។
  4. ដកជួរខាងលើនៃជួរអាទិភាពកាត់បន្ថយវាដោយលេខ 1 ហើយប្រសិនបើវាមិនមែនសូន្យរុញវាត្រឡប់ទៅជួរអាទិភាពវិញ។
  5. តម្លៃអប្បបរមាគឺជាផលបូកនៃការ៉េនៃតម្លៃដែលមាននៅក្នុងជួរអាទិភាព។

ស្មុគស្មាញពេលវេលា = O (n + k * log (c))
ភាពស្មុគស្មាញនៃលំហ = O (គ)
ដែលគគឺថេរដែលស្មើនឹងចំនួនតួអក្សរពិសេសនៅក្នុងខ្សែអក្សរ។ ចាប់តាំងពីយើងកំពុងដកធាតុ k ចេញពីជួរអាទិភាព។ ការបញ្ចូលនិងការដកចេញពីជួរអាទិភាព O (log N) ពេលវេលា។ ដូច្នេះកត្តាមួយបានកើតឡើង។ ភាពស្មុគស្មាញនៃលំហគឺដោយសារតែយើងបានបង្កើតអារេប្រេកង់ប៉ុន្តែចាប់តាំងពីទំហំនៃប្រេកង់គឺឯករាជ្យនៃធាតុបញ្ចូល។ ដូច្នេះហើយភាពស្មុគស្មាញនៃលំហគឺថេរ។

លេខកូដដើម្បីស្វែងរកចំនួនអប្បបរមានៃការ៉េនៃចំនួនតួអក្សរនៅក្នុងខ្សែអក្សរដែលបានផ្តល់បន្ទាប់ពីដកតួអក្សរ 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