Algorithm: Leetcode Contest 384

First Happy Chinese New Year!

Number of Subarrays That Match a Pattern I

You are given a 0-indexed integer array nums of size n, and a 0-indexed integer array pattern of size m consisting of integers -1, 0, and 1.

A subarray nums[i..j] of size m + 1 is said to match the pattern if the following conditions hold for each element pattern[k]:

• nums[i + k + 1] > nums[i + k] if pattern[k] == 1.
• nums[i + k + 1] == nums[i + k] if pattern[k] == 0.
• nums[i + k + 1] < nums[i + k] if pattern[k] == -1.

Return the count of subarrays in nums that match the pattern.

Solution

class Solution {
    public int countMatchingSubarrays(int[] nums, int[] pattern) {
        int[] numPattern = new int[nums.length];
        
        for(int i = 0; i <= nums.length - 2; i++) {
            if (nums[i] < nums[i + 1]) {
                numPattern[i] = 1;
            } else if (nums[i] > nums[i + 1]) {
                numPattern[i] = -1;
            } else {
                numPattern[i] = 0;
            }
        }
        
        return countMatch(numPattern, pattern);
    }
    
    private int countMatch(int[] origin, int[] match) {
        int count = 0;
        for(int i = 0; i + match.length < origin.length; i++) {
            int index = 0;
            for(; index < match.length; index++) {
                if (origin[i + index] != match[index]) {
                    break;
                }
            }
            if (index == match.length) {
                count++;
            }
        }
        
        return count;
    }
}

relatively easy challenge, the challenging part is how to count the match array from original array.

Maximum Palindromes After Operations

You are given a 0-indexed string array words having length n and containing 0-indexed strings.

You are allowed to perform the following operation any number of times (including zero):

• Choose integers i, j, x, and y such that 0 <= i, j < n, 0 <= x < words[i].length, 0 <= y < words[j].length, and swap the characters words[i][x] and words[j][y].

Return an integer denoting the maximum number of

palindromes

words can contain, after performing some operations.

Solution

class Solution {
    public int maxPalindromesAfterOperations(String[] words) {
        int[] counter = new int[26];
        int[] wordSize = new int[words.length];
        int res = 0;
        
        String word = "";
        for(int i = 0; i < words.length; i++) {
            word = words[i];
            wordSize[i] = word.length();
            
            for(char c: word.toCharArray()) {
                counter[c - 'a']++;
            }
        }
        
        int pairs = 0;
        for(int i: counter) {
            pairs += i/2;
        }
        
        Arrays.sort(wordSize);
        
        for (int size: wordSize) {
            pairs -= size / 2;
            if (pairs < 0) {
                break;
            }
            res++;
        }
        
        return res;
        
    }
}

Retro

Since the description explicitly mentioned

perform the following operation any number

It implies that we should do micro-manipulation, e.g. swap character and count the steps,

Instead we should solve it at a high value, skip the details and focus on the final state.

In this solution, we just count how may character pairs in words, then figure out how many palindrome string can be made up.

In this way, we don’t need to go into details, from the final state to find out the solution.