Change minimum characters to satisfy one of three conditions

Hash Table String Counting Prefix Sum

37.8% acceptance

Feb 25, 2026

336

346

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: Every letter in a is strictly less than every letter in b in the alphabet. Every letter in b is strictly less than every letter in a in the alphabet. Both a and b consist of only one distinct letter. Return the minimum number of operations needed to achieve your goal.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_characters(a: String, b: String) -> i32 {
    let la = a.len() as i32;
    let lb = b.len() as i32;
    let mut freq_a = [0i32; 26];
    let mut freq_b = [0i32; 26];
    for c in a.bytes() { freq_a[(c - b'a') as usize] += 1; }
    for c in b.bytes() { freq_b[(c - b'a') as usize] += 1; }

    // Prefix sums
    let mut pre_a = [0i32; 27];
    let mut pre_b = [0i32; 27];
    for i in 0..26 {
      pre_a[i + 1] = pre_a[i] + freq_a[i];
      pre_b[i + 1] = pre_b[i] + freq_b[i];
    }

    let mut ans = la + lb; // worst case: condition 3 with all changed
    for c in 0..26 {
      // Condition 3: all same letter c
      ans = ans.min((la - freq_a[c]) + (lb - freq_b[c]));
      if c < 25 {
        // Condition 1: all a < threshold (c+1), all b >= threshold (c+1)
        // cost = chars in a at positions >= c+1 + chars in b at positions < c+1
        let cost1 = (la - pre_a[c + 1]) + pre_b[c + 1];
        // Condition 2: all b < threshold (c+1), all a >= threshold (c+1)
        let cost2 = (lb - pre_b[c + 1]) + pre_a[c + 1];
        ans = ans.min(cost1).min(cost2);
      }
    }
    ans
  }
}