# Change Minimum Characters to Satisfy One of Three Conditions
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions)
Canonical: https://scaleengineer.com/dsa/problems/change-minimum-characters-to-satisfy-one-of-three-conditions
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Hash Table, String
---
## Problem
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._

**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 <= 105`
* `a` and `b` consist only of lowercase letters.

# Approaches
## Brute-Force Calculation for Each Condition
This approach directly translates the problem statement into code. It calculates the minimum operations required for each of the three conditions separately and then returns the overall minimum. For each condition, it iterates through all 26 possible lowercase letters, treating them as either a target character (for condition 3) or a boundary (for conditions 1 and 2). The cost for each potential character is found by iterating through the input strings `a` and `b`.
**Time:** O(K * (N + M)), where N and M are the lengths of strings `a` and `b`, and K is the size of the alphabet (26). Since K is a constant, the complexity is linear, O(N + M), but with a higher constant factor than the optimized approach. · **Space:** O(1), as we only use a few variables to store counts and the minimum operations.
**Pros:** Simple to understand and implement.; Low memory usage as it only requires a few variables.
**Cons:** Less efficient than the optimized approach due to nested loops, which result in repeated traversals of the input strings.; The time complexity has a larger constant factor (26) compared to the prefix sum method.
### Explanation
The problem asks for the minimum operations to satisfy one of three conditions. We can find the minimum cost for each condition independently and then take the minimum of these three costs.

1.  **Condition 1: All letters in `a` are strictly less than all letters in `b`.**
    This can be achieved by choosing a boundary character `c` (from 'b' to 'z'). We then change all characters in `a` that are greater than or equal to `c` and all characters in `b` that are less than `c`. We iterate through all 25 possible boundaries `c` from 'b' to 'z', calculate the cost for each, and take the minimum.

2.  **Condition 2: All letters in `b` are strictly less than all letters in `a`.**
    This is symmetric to condition 1. We iterate through the same boundaries `c` from 'b' to 'z'. For each `c`, we change all characters in `b` that are greater than or equal to `c` and all characters in `a` that are less than `c`.

3.  **Condition 3: Both `a` and `b` consist of only one distinct letter.**
    This implies that all characters in both strings must be converted to the same character `c`. We iterate through all 26 possible target characters `c` from 'a' to 'z'. The cost is the number of characters in `a` not equal to `c` plus the number of characters in `b` not equal to `c`.

The final answer is the minimum cost found across all three conditions.

```java
class Solution {
    public int minCharacters(String a, String b) {
        int n = a.length();
        int m = b.length();
        int minOps = n + m; // Max possible operations

        // Condition 1: a < b
        for (char c = 'b'; c <= 'z'; c++) {
            int currentOps = 0;
            for (char ch : a.toCharArray()) {
                if (ch >= c) {
                    currentOps++;
                }
            }
            for (char ch : b.toCharArray()) {
                if (ch < c) {
                    currentOps++;
                }
            }
            minOps = Math.min(minOps, currentOps);
        }

        // Condition 2: b < a
        for (char c = 'b'; c <= 'z'; c++) {
            int currentOps = 0;
            for (char ch : b.toCharArray()) {
                if (ch >= c) {
                    currentOps++;
                }
            }
            for (char ch : a.toCharArray()) {
                if (ch < c) {
                    currentOps++;
                }
            }
            minOps = Math.min(minOps, currentOps);
        }

        // Condition 3: a and b are uniform
        for (char c = 'a'; c <= 'z'; c++) {
            int currentOps = 0;
            for (char ch : a.toCharArray()) {
                if (ch != c) {
                    currentOps++;
                }
            }
            for (char ch : b.toCharArray()) {
                if (ch != c) {
                    currentOps++;
                }
            }
            minOps = Math.min(minOps, currentOps);
        }

        return minOps;
    }
}
```
### Algorithm
1. Initialize `min_ops` to a value larger than any possible result, such as `a.length() + b.length()`.
2. **Calculate cost for Condition 1 (all `a` < all `b`):**
   - Loop through each character `c` from 'b' to 'z'. This `c` acts as the boundary.
   - For each `c`, calculate the operations `ops` needed. This is the sum of characters in `a` that are `>= c` and characters in `b` that are `< c`.
   - Update `min_ops = min(min_ops, ops)`.
3. **Calculate cost for Condition 2 (all `b` < all `a`):**
   - This is symmetric to condition 1. Loop through each character `c` from 'b' to 'z'.
   - For each `c`, calculate `ops` by counting characters in `b` that are `>= c` and characters in `a` that are `< c`.
   - Update `min_ops = min(min_ops, ops)`.
4. **Calculate cost for Condition 3 (both strings have one distinct character):**
   - Loop through each character `c` from 'a' to 'z'. This `c` is the target character.
   - For each `c`, calculate `ops` by counting characters in `a` and `b` that are not equal to `c`.
   - Update `min_ops = min(min_ops, ops)`.
5. Return `min_ops`.

## Optimized Calculation using Frequency Map and Prefix Sums
This approach significantly optimizes the calculation by avoiding repeated traversals of the strings. It starts by creating frequency maps for both strings in a single pass. Then, it uses these maps to efficiently calculate the costs. For conditions 1 and 2, it further computes prefix sums on the frequency maps, which allows calculating the number of changes for any boundary character in O(1) time.
**Time:** O(N + M + K), where N and M are string lengths and K is the alphabet size (26). This simplifies to O(N + M) because the main work is the initial pass over the strings. · **Space:** O(K) for the frequency and prefix sum arrays, where K is the alphabet size (26). Since K is a fixed constant, this is considered O(1) space.
**Pros:** Highly efficient, with a time complexity linear in the total length of the strings.; Processes each string only once, making it much faster for large inputs than the brute-force approach.
**Cons:** Slightly more complex to implement due to the use of auxiliary arrays for frequencies and prefix sums.; Uses a small amount of extra space for the arrays, though it's constant space.
### Explanation
The core idea is to pre-calculate character frequencies to avoid re-scanning the strings for every possible case.

1.  **Frequency Maps:** First, we iterate through strings `a` and `b` once to populate two frequency arrays, `freqA` and `freqB`, of size 26. `freqA[i]` will hold the count of character `'a' + i` in string `a`.

2.  **Cost for Condition 3:** The cost to make both strings uniform with character `c` is `(n - freqA[c-'a']) + (m - freqB[c-'a'])`. We can find the minimum cost for this condition by iterating through all 26 characters and finding the one that minimizes this value. This is equivalent to finding the character `c` that maximizes the sum `freqA[c-'a'] + freqB[c-'a']`.

3.  **Cost for Conditions 1 & 2:** To quickly calculate the costs for conditions 1 and 2, we build prefix sum arrays (`prefixA`, `prefixB`) from our frequency maps. `prefixA[i]` stores the total count of characters less than or equal to `'a' + i` in string `a`.
    - For a given split point between character `i` and `i+1`:
        - The cost for condition 1 (a < b) is the number of characters in `a` greater than `i` plus the number of characters in `b` less than or equal to `i`. This can be calculated in O(1) as `(n - prefixA[i]) + prefixB[i]`.
        - The cost for condition 2 (b < a) is calculated symmetrically as `(m - prefixB[i]) + prefixA[i]`.
    - We iterate through all 25 possible split points (from 'a'/'b' to 'y'/'z') and find the minimum operations for these two conditions.

Finally, we return the minimum of the costs calculated for the three conditions.

```java
class Solution {
    public int minCharacters(String a, String b) {
        int n = a.length();
        int m = b.length();

        int[] freqA = new int[26];
        int[] freqB = new int[26];

        for (char c : a.toCharArray()) {
            freqA[c - 'a']++;
        }
        for (char c : b.toCharArray()) {
            freqB[c - 'a']++;
        }

        // Condition 3: Both a and b consist of only one distinct letter
        int cost3 = n + m;
        for (int i = 0; i < 26; i++) {
            cost3 = Math.min(cost3, (n - freqA[i]) + (m - freqB[i]));
        }

        int minOps = cost3;

        // For conditions 1 and 2, use prefix sums
        int[] prefixA = new int[26];
        int[] prefixB = new int[26];
        prefixA[0] = freqA[0];
        prefixB[0] = freqB[0];
        for (int i = 1; i < 26; i++) {
            prefixA[i] = prefixA[i-1] + freqA[i];
            prefixB[i] = prefixB[i-1] + freqB[i];
        }

        // Iterate through possible split characters from 'b' to 'z'
        // A split after character 'i' means one string is <= 'a'+i and the other is > 'a'+i
        for (int i = 0; i < 25; i++) {
            // Condition 1: a < b
            // Changes in a: make all chars <= 'a'+i. Count of chars > 'a'+i is n - prefixA[i]
            // Changes in b: make all chars > 'a'+i. Count of chars <= 'a'+i is prefixB[i]
            int cost1 = (n - prefixA[i]) + prefixB[i];
            minOps = Math.min(minOps, cost1);

            // Condition 2: b < a
            // Changes in b: make all chars <= 'a'+i. Count of chars > 'a'+i is m - prefixB[i]
            // Changes in a: make all chars > 'a'+i. Count of chars <= 'a'+i is prefixA[i]
            int cost2 = (m - prefixB[i]) + prefixA[i];
            minOps = Math.min(minOps, cost2);
        }

        return minOps;
    }
}
```
### Algorithm
1. Create frequency arrays `freqA` and `freqB` of size 26.
2. Populate `freqA` and `freqB` by iterating through strings `a` and `b` once.
3. Calculate `cost3`, the minimum cost for condition 3. This is `a.length() + b.length() - max(freqA[i] + freqB[i])` for `i` from 0 to 25. Initialize `min_ops` with this value.
4. Create prefix sum arrays `prefixA` and `prefixB` from the frequency arrays. `prefixA[i]` will store the count of characters `<= 'a' + i`.
5. Loop `i` from 0 to 24 (representing the split point after character `'a' + i`).
   - Calculate the cost for condition 1 at this split: `cost1_i = (a.length() - prefixA[i]) + prefixB[i]`.
   - Calculate the cost for condition 2 at this split: `cost2_i = (b.length() - prefixB[i]) + prefixA[i]`.
   - Update `min_ops = min(min_ops, cost1_i, cost2_i)`.
6. Return `min_ops`.

# Solutions
### Java

```java
class Solution {
private
  int ans;
public
  int minCharacters(String a, String b) {
    int m = a.length(), n = b.length();
    int[] cnt1 = new int[26];
    int[] cnt2 = new int[26];
    for (int i = 0; i < m; ++i) {
      ++cnt1[a.charAt(i) - 'a'];
    }
    for (int i = 0; i < n; ++i) {
      ++cnt2[b.charAt(i) - 'a'];
    }
    ans = m + n;
    for (int i = 0; i < 26; ++i) {
      ans = Math.min(ans, m + n - cnt1[i] - cnt2[i]);
    }
    f(cnt1, cnt2);
    f(cnt2, cnt1);
    return ans;
  }
private
  void f(int[] cnt1, int[] cnt2) {
    for (int i = 1; i < 26; ++i) {
      int t = 0;
      for (int j = i; j < 26; ++j) {
        t += cnt1[j];
      }
      for (int j = 0; j < i; ++j) {
        t += cnt2[j];
      }
      ans = Math.min(ans, t);
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minCharacters(string a, string b) {
    int m = a.size(), n = b.size();
    vector<int> cnt1(26);
    vector<int> cnt2(26);
    for (char &c : a)
      ++cnt1[c - 'a'];
    for (char &c : b)
      ++cnt2[c - 'a'];
    int ans = m + n;
    for (int i = 0; i < 26; ++i)
      ans = min(ans, m + n - cnt1[i] - cnt2[i]);
    auto f = [&](vector<int> &cnt1, vector<int> &cnt2) {
      for (int i = 1; i < 26; ++i) {
        int t = 0;
        for (int j = i; j < 26; ++j)
          t += cnt1[j];
        for (int j = 0; j < i; ++j)
          t += cnt2[j];
        ans = min(ans, t);
      }
    };
    f(cnt1, cnt2);
    f(cnt2, cnt1);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minCharacters(self, a: str, b: str) -> int: def f(cnt1, cnt2): for i in range(1, 26): t = sum(cnt1[i:]) + sum(cnt2[: i]) nonlocal ans ans = min(ans, t) m, n = len(a), len(b) cnt1 = [0] * 26 cnt2 = [0] * 26 for c in a: cnt1[ord(c) - ord('a')] += 1 for c in b: cnt2[ord(c) - ord('a')] += 1 ans = m + n for c1, c2 in zip(cnt1, cnt2): ans = min(ans, m + n - c1 - c2) f(cnt1, cnt2) f(cnt2, cnt1) return ans

```