Change Minimum Characters to Satisfy One of Three Conditions

Med

#1591Time: 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.

Patterns

Counting Prefix Sum

Data structures

Hash Table String

Prompt

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 <= 10⁵
a and b consist only of lowercase letters.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

Initialize min_ops to a value larger than any possible result, such as a.length() + b.length().
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).
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).
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).
Return min_ops.

Walkthrough

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.

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.
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.
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.

1class Solution {2    public int minCharacters(String a, String b) {3        int n = a.length();4        int m = b.length();5        int minOps = n + m; // Max possible operations6 7        // Condition 1: a < b8        for (char c = 'b'; c <= 'z'; c++) {9            int currentOps = 0;10            for (char ch : a.toCharArray()) {11                if (ch >= c) {12                    currentOps++;13                }14            }15            for (char ch : b.toCharArray()) {16                if (ch < c) {17                    currentOps++;18                }19            }20            minOps = Math.min(minOps, currentOps);21        }22 23        // Condition 2: b < a24        for (char c = 'b'; c <= 'z'; c++) {25            int currentOps = 0;26            for (char ch : b.toCharArray()) {27                if (ch >= c) {28                    currentOps++;29                }30            }31            for (char ch : a.toCharArray()) {32                if (ch < c) {33                    currentOps++;34                }35            }36            minOps = Math.min(minOps, currentOps);37        }38 39        // Condition 3: a and b are uniform40        for (char c = 'a'; c <= 'z'; c++) {41            int currentOps = 0;42            for (char ch : a.toCharArray()) {43                if (ch != c) {44                    currentOps++;45                }46            }47            for (char ch : b.toCharArray()) {48                if (ch != c) {49                    currentOps++;50                }51            }52            minOps = Math.min(minOps, currentOps);53        }54 55        return minOps;56    }57}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Create frequency arrays freqA and freqB of size 26.
Populate freqA and freqB by iterating through strings a and b once.
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.
Create prefix sum arrays prefixA and prefixB from the frequency arrays. prefixA[i] will store the count of characters <= 'a' + i.
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).
Return min_ops.

Walkthrough

The core idea is to pre-calculate character frequencies to avoid re-scanning the strings for every possible case.

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.
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'].
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.

1class Solution {2    public int minCharacters(String a, String b) {3        int n = a.length();4        int m = b.length();5 6        int[] freqA = new int[26];7        int[] freqB = new int[26];8 9        for (char c : a.toCharArray()) {10            freqA[c - 'a']++;11        }12        for (char c : b.toCharArray()) {13            freqB[c - 'a']++;14        }15 16        // Condition 3: Both a and b consist of only one distinct letter17        int cost3 = n + m;18        for (int i = 0; i < 26; i++) {19            cost3 = Math.min(cost3, (n - freqA[i]) + (m - freqB[i]));20        }21 22        int minOps = cost3;23 24        // For conditions 1 and 2, use prefix sums25        int[] prefixA = new int[26];26        int[] prefixB = new int[26];27        prefixA[0] = freqA[0];28        prefixB[0] = freqB[0];29        for (int i = 1; i < 26; i++) {30            prefixA[i] = prefixA[i-1] + freqA[i];31            prefixB[i] = prefixB[i-1] + freqB[i];32        }33 34        // Iterate through possible split characters from 'b' to 'z'35        // A split after character 'i' means one string is <= 'a'+i and the other is > 'a'+i36        for (int i = 0; i < 25; i++) {37            // Condition 1: a < b38            // Changes in a: make all chars <= 'a'+i. Count of chars > 'a'+i is n - prefixA[i]39            // Changes in b: make all chars > 'a'+i. Count of chars <= 'a'+i is prefixB[i]40            int cost1 = (n - prefixA[i]) + prefixB[i];41            minOps = Math.min(minOps, cost1);42 43            // Condition 2: b < a44            // Changes in b: make all chars <= 'a'+i. Count of chars > 'a'+i is m - prefixB[i]45            // Changes in a: make all chars > 'a'+i. Count of chars <= 'a'+i is prefixA[i]46            int cost2 = (m - prefixB[i]) + prefixA[i];47            minOps = Math.min(minOps, cost2);48        }49 50        return minOps;51    }52}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  int ans;4public5  int minCharacters(String a, String b) {6    int m = a.length(), n = b.length();7    int[] cnt1 = new int[26];8    int[] cnt2 = new int[26];9    for (int i = 0; i < m; ++i) {10      ++cnt1[a.charAt(i) - 'a'];11    }12    for (int i = 0; i < n; ++i) {13      ++cnt2[b.charAt(i) - 'a'];14    }15    ans = m + n;16    for (int i = 0; i < 26; ++i) {17      ans = Math.min(ans, m + n - cnt1[i] - cnt2[i]);18    }19    f(cnt1, cnt2);20    f(cnt2, cnt1);21    return ans;22  }23private24  void f(int[] cnt1, int[] cnt2) {25    for (int i = 1; i < 26; ++i) {26      int t = 0;27      for (int j = i; j < 26; ++j) {28        t += cnt1[j];29      }30      for (int j = 0; j < i; ++j) {31        t += cnt2[j];32      }33      ans = Math.min(ans, t);34    }35  }36}

1class Solution {2public:3  int minCharacters(string a, string b) {4    int m = a.size(), n = b.size();5    vector<int> cnt1(26);6    vector<int> cnt2(26);7    for (char &c : a)8      ++cnt1[c - 'a'];9    for (char &c : b)10      ++cnt2[c - 'a'];11    int ans = m + n;12    for (int i = 0; i < 26; ++i)13      ans = min(ans, m + n - cnt1[i] - cnt2[i]);14    auto f = [&](vector<int> &cnt1, vector<int> &cnt2) {15      for (int i = 1; i < 26; ++i) {16        int t = 0;17        for (int j = i; j < 26; ++j)18          t += cnt1[j];19        for (int j = 0; j < i; ++j)20          t += cnt2[j];21        ans = min(ans, t);22      }23    };24    f(cnt1, cnt2);25    f(cnt2, cnt1);26    return ans;27  }28};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem