Algorithm: Leetcode Contest 389

3084. Count Substrings Starting and Ending with Given Character

Solution

class Solution {
    public long countSubstrings(String s, char c) {
        // count the occurance 
        
        long count = 0;
        for(char a: s.toCharArray()) {
            if (a == c) {
                count++;
            }
        }
        
        long res = 0;
        while(count != 0) {
            res += count--;
        }
        
        return res;
    }
}

Retro

Actually this problem is not that hard as long as we can find its essence.

No matter the position of each character, as long as its count is determined, then the answer is determined.

Find the relationship between the count and answer is the most important point of this problem

3085. Minimum Deletions to Make String K-Special

Solution

class Solution {
    public int minimumDeletions(String word, int k) {
        
        int[] stats = new int[26];
        
        for(char c: word.toCharArray()) {
            stats[c - 'a']++;
        }
        
        int min = Integer.MAX_VALUE;
        int ops = 0, deleted = 0;
        
        Arrays.sort(stats);
        for(int i = 0; i < stats.length; i++) {
            if (stats[i] == 0) {
                continue;
            }
            
            ops = 0;
            for(int j = i + 1; j < stats.length; j++) {
                if (stats[j] - stats[i] <= k) {
                    continue;
                }
                
                ops += stats[j] - stats[i] - k;
            }
            
            min = Math.min(min, ops + deleted);
            
            deleted += stats[i];
        }
        
        return min;
    }
}

Retro

I didn’t figure out the solution within the contest time.

The missing part is sort

I tried to solve the problem without sorting, then hardly able to determine how to handle each freq.

In my original solution, instead of making current index as less frequent one, I mark it as average. any other frequent should fall into [-k/2, +k/2] range. Then I find it doesn’t work cause the range is “fake”.

Sorting can solve this problem, cause it contains a very strong implication: frequency of current item is the base line.

It cannot be overemphasized that when we solve the array problem, sorting need to always be considered, just like Trie to string problem.