1737. Change Minimum Characters to Satisfy One of Three Conditions

Input: a = "aba", b = "caa"
Output: 2
Explanation: Consider the best way to make each condition true:
1) Change b to "ccc" in 2 operations, then every letter in a is less than every letter in b.
2) Change a to "bbb" and b to "aaa" in 3 operations, then every letter in b is less than every letter in a.
3) Change a to "aaa" and b to "aaa" in 2 operations, then a and b consist of one distinct letter.
The best way was done in 2 operations (either condition 1 or condition 3).

Input: a = "dabadd", b = "cda"
Output: 3
Explanation: The best way is to make condition 1 true by changing b to "eee".

Rust Solution

struct Solution;

impl Solution {
    fn min_characters(a: String, b: String) -> i32 {
        let a: Vec<u8> = a.bytes().collect();
        let b: Vec<u8> = b.bytes().collect();
        let count_a = Self::check(&a);
        let count_b = Self::check(&b);
        let mut prefix_a = vec![0; 26];
        let mut prev_a = 0;
        let mut prefix_b = vec![0; 26];
        let mut prev_b = 0;
        for i in 0..26 {
            prefix_a[i] = prev_a;
            prev_a += count_a[i];
            prefix_b[i] = prev_b;
            prev_b += count_b[i];
        }
        let mut postfix_a = vec![0; 26];
        let mut next_a = 0;
        let mut postfix_b = vec![0; 26];
        let mut next_b = 0;
        for i in (0..26).rev() {
            postfix_a[i] = next_a;
            next_a += count_a[i];
            postfix_b[i] = next_b;
            next_b += count_b[i];
        }
        let mut max = 0;
        let mut max_a = 0;
        let mut max_b = 0;
        for i in 0..26 {
            max_a = max_a.max(count_a[i]);
            max_b = max_b.max(count_b[i]);
        }
        max = max.max(max_a + max_b);
        for i in 1..26 {
            max = max.max(prefix_a[i] + postfix_b[i - 1]);
            max = max.max(prefix_b[i] + postfix_a[i - 1]);
        }
        (a.len() + b.len() - max) as i32
    }

    fn check(s: &[u8]) -> Vec<usize> {
        let mut count: Vec<usize> = vec![0; 26];
        for b in s {
            count[(b - b'a') as usize] += 1;
        }
        count
    }
}

#[test]
fn test() {
    let a = "aba".to_string();
    let b = "caa".to_string();
    let res = 2;
    assert_eq!(Solution::min_characters(a, b), res);
    let a = "dabadd".to_string();
    let b = "cda".to_string();
    let res = 3;
    assert_eq!(Solution::min_characters(a, b), res);
    let a = "acac".to_string();
    let b = "bd".to_string();
    let res = 1;
    assert_eq!(Solution::min_characters(a, b), res);
}