You are given two strings a and b that consist of lowercase letters. In one operation, you can change any character in a or b to any lowercase letter.
Your goal is to satisfy one of the following three conditions:
a is strictly less than every letter in b in the alphabet.b is strictly less than every letter in a in the alphabet.a and b consist of only one distinct letter.Return the minimum number of operations needed to achieve your goal.
Example 1:
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).
Example 2:
Input: a = "dabadd", b = "cda" Output: 3 Explanation: The best way is to make condition 1 true by changing b to "eee".
Constraints:
1 <= a.length, b.length <= 105a and b consist only of lowercase letters.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);
}