Scale Engineer

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
CountingPrefix Sum
Data structures
Hash TableString

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 <= 105
  • 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

  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.

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.

  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.

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;    }}

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.

Solutions

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);    }  }}

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 →

Next problem