2024-10-08: In go, given a string word and an integer k, determine whether the string can be made into a k special string by deleting the minimum number of characters. Where k special strings satisfy the frequency of occurrence of any two characters in th

2024-10-08: In go, given a string word and an integer k, determine whether the string can be made k-special by deleting the minimum number of characters.

where the k special string satisfies that the absolute value of the difference in the frequency of occurrence of any two characters in the string does not exceed k.

You can write an algorithm to calculate the minimum number of characters that need to be deleted to make a given string word a k-special string.

Input: word = "aabcaba", k = 0.

Output: 3.

Explanation: You can delete 2 "a" and 1 "c" to make word a 0 special string. word becomes "baba", when freq('a') == freq('b') == 2.

Answer 2024-10-08:

chatgpt

Title from leetcode3085.

The broad steps are as follows:

1. Create an integer slice of length 26cntThe word count is used to count the wordsword The number of times each letter appears in the

2. Willcnt The values are sorted so that they are in decreasing order of occurrence.

3. Initialize variablesmaxSave is 0 to record the maximum number of characters saved.

4. Iterate through the sortedcnt Slice, for the number of times each letter appears base:

• Initializing Variablessum is 0 to record the total number of characters if base+k characters are retained.

• Iterate through the cnt slices starting at the current position, summing the number of occurrences of the character with the lesser of base+k tosum。

• updatemaxSave because ofsum collaboration withmaxSave The greater of.

5. Calculate the final number of characters to be deleted, i.e. len(word) minusmaxSave The value of the

Total time complexity: the sorting operation should be the most time-consuming part of the code, with a time complexity of O(nlog(n)), with n being the word length. The next traversal operation has a time complexity of O(26 * n) because for each character we need to traverse the cnt slice. The final total time complexity is O(nlog(n) + 26n), which is approximately equal to O(nlog(n))。

Total extra space complexity: in addition to the input parameters, the code uses an integer slice cnt of length 26, so the extra space complexity is O(26) (constant level).

The complete code for go is as follows:

package main

import (
	"fmt"
	"slices"
)

func minimumDeletions(word string, k int) int {
	cnt := make([]int, 26)
	for _, b := range word {
		cnt[b-'a']++
	}
	(cnt)

	maxSave := 0
	for i, base := range cnt {
		sum := 0
		for _, c := range cnt[i:] {
			sum += min(c, base+k) // up to base+k classifier for individual things or people, general, catch-all classifier
		}
		maxSave = max(maxSave, sum)
	}
	return len(word) - maxSave
}
func main() {
	word := "aabcaba"
	k:=0
	(minimumDeletions(word, k))
}

The complete code for rust is below:

use std::cmp::{max, min};

fn minimum_deletions(word: &str, k: i32) -> i32 {
    let mut cnt: [i32; 26] = [0; 26];
    for b in () {
        cnt[(b as u8 - b'a') as usize] += 1;
    }
    slice_sort(&mut cnt);

    let mut max_save = 0;
    for (i, &base) in ().enumerate() {
        let mut sum = 0;
        for &c in &cnt[i..] {
            sum += min(c, base + k); // maximum retention base+k classifier for individual things or people, general, catch-all classifier
        }
        max_save = max(max_save, sum);
    }
    (() as i32) - max_save
}

fn slice_sort(slice: &mut [i32; 26]) {
    slice.sort_unstable();
}

fn main() {
    let word = "aabcaba";
    let k = 0;
    println!("{}", minimum_deletions(word, k));
}