Weekly Contest 374, Leetcode

Solutions for weekly contest 374.

B Minimum Number of Coins to be Added

Analysis

We have some conslusions:

1. We can sort coins array, because of a + b = b + a.

2. Induction. Suppose we have that [1, s] can be obtainable, for a new integer x, we must have that [max(s, x), s + x] are obtainable.

Code

rust

/// get answer in O(nlogn + target)/O(1)
pub fn minimum_added_coins(mut coins: Vec<i32>, target: i32) -> i32 {
    coins.sort_unstable();
    let mut ans = 0;
    // [1, s - 1] is obtainable, s is not
    let (mut s, mut i) = (1, 0);
    while s <= target {
        if i < coins.len() && coins[i] <= s {
            // s is obtainable
            s += coins[i];
            i += 1;
        } else {
            // [s, coins[i]] is not obtainable
            s += s;
            ans += 1;
        }
    }
    ans
}

C Count Complete Substrings

Analysis

We have some conslusions:

1. The difference characters in a complete substring is at most 26, that's a...z.
2. The length of a complete substring is in [k, 2 * k, ... 26 * k].

So we can solve this problem using sliding window.

Code

rust

/// get ans in O(C^2 * n)/O(C)
/// keywords: sliding window
pub fn count_complete_substrings(word: String, k: i32) -> i32 {
    let mut ans = 0;
    for i in 1..=26 {
        ans += helper_c(word.as_bytes(), k, i);
    }
    ans
}

/// get ans in O(C * n)/O(C)
fn helper_c(word: &[u8], k: i32, cnt: i32) -> i32 {
    if k * cnt > word.len() as i32 {
        return 0;
    }
    let mut ans = 0;
    let size = (k * cnt) as usize; // the size of sliding window is k * cnt

    let mut ht = [0; 26];
    let (mut l, mut r) = (0usize, 0usize);
    while r < word.len() {
        let i = (word[r] - b'a') as usize;
        if size > 1 && r > 0 {
            let j = (word[r - 1] - b'a') as usize;
            if i > j + 2 || i + 2 < j {
                l = r;
                ht.fill(0);
            }
        }
        ht[i] += 1;
        if r - l + 1 == size {
            let mut flag = true;
            for i in 0..26 {
                if ht[i] > 0 && ht[i] != k {
                    flag = false;
                    break;
                }
            }
            if flag {
                ans += 1;
            }
            ht[(word[l] - b'a') as usize] -= 1;
            l += 1;
        }
        r += 1;
    }
    ans
}