Change Minimum Characters to Satisfy One of Three Conditions - Solution & Explanation
Problem Statement
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
ais strictly less than every letter inbin the alphabet. - Every letter in
bis strictly less than every letter inain the alphabet. - Both
aandbconsist 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 <= 105aandbconsist only of lowercase letters.
Approach Overview
Problem Overview: You get two lowercase strings a and b. Modify the minimum number of characters so one of three conditions holds: every character in a is strictly less than every character in b, every character in b is strictly less than every character in a, or both strings contain only one distinct character.
The constraints are small for the alphabet (26 letters) but large for string length. That means the right strategy focuses on frequency counting instead of comparing characters directly.
Approach 1: Direct Count and Compare (O(n + 26), space O(26))
Start by building two frequency arrays of size 26 for a and b. Each index represents a letter from 'a' to 'z'. With these counts, evaluate the three required conditions.
For the third condition (both strings use a single identical character), iterate through all 26 letters and compute how many characters must change so both strings become that letter. The minimum across all letters is the cost.
For the first two conditions, test every possible split character c where letters in one string must be <= c and the other > c. Count how many characters violate this rule using the frequency arrays. This approach relies on simple counting and works well because the alphabet size is constant.
Approach 2: Prefix Sums for Strictly Less Condition (O(n + 26), space O(26))
This approach improves the evaluation of lexicographic conditions using prefix sums over the frequency arrays. After counting characters, build prefix sums where prefix[i] stores the number of characters with index ā¤ i.
For a split character i, you instantly know how many characters in a are ā¤ i and how many in b are ā¤ i. From this you derive how many characters violate the strictly less requirement. Iterate over all 25 possible split points (aāy) and compute the required modifications.
Prefix sums remove repeated counting work and make the condition checks constant time per letter. The total complexity stays linear in the string length.
Both strategies rely heavily on character frequencies, making them classic applications of counting and prefix sum techniques on string data.
Recommended for interviews: The prefix-sum counting approach. Interviewers expect you to reduce the problem to frequency arrays over the 26-letter alphabet and evaluate split points efficiently. Starting with direct counting shows understanding, but using prefix sums demonstrates stronger algorithmic thinking.
Approach 1: Prefix Sums for Strictly Less Condition
This approach uses prefix sums to efficiently calculate the minimum operations required to make all letters in one string strictly less than all letters in the other string. The essential idea is to transform frequency counts into cumulative counts (prefix sums) to get faster comparisons between possible transformation states.
The function calculates the frequency of each character in the input strings a and b. It then turns these frequencies into prefix sums. By using prefix sums, we can efficiently calculate how many characters need to change to satisfy the first two conditions: making a strictly less than b or b strictly less than a.
Code
Python
JavaScript
Complexity
Time Complexity: O(n + m), where n is the length of a and m is the length of b, since we loop over each string to build frequency counts and prefix sums.
Space Complexity: O(1), since the space used is constant and not dependent on the input size.
Approach 2: Direct Count and Compare
This approach works by directly counting the necessary transformations. We evaluate each transformation possibility directly by counting how many elements need to change to satisfy each of the conditions.
By using integer arrays to count and partially sum frequencies, we evaluate all feasible character transformations to reach the desired string states. We directly compute the changes needed to make all elements in 'a' less than 'b' or vice versa, or to make both uniform strings.
Complexity
Time Complexity: O(n + m).
Space Complexity: O(1).
Approach 3: Counting + Enumeration
First, we count the number of occurrences of each letter in strings a and b, denoted as cnt_1 and cnt_2.
Then, we consider condition 3, i.e., every letter in a and b is the same. We just need to enumerate the final letter c, and then count the number of letters in a and b that are not c. This is the number of characters that need to be changed.
Next, we consider conditions 1 and 2, i.e., every letter in a is less than every letter in b, or every letter in b is less than every letter in a. For condition 1, we make all characters in string a less than character c, and all characters in string b not less than c. We enumerate c to find the smallest answer. Condition 2 is similar.
The final answer is the minimum of the above three cases.
The time complexity is O(m + n + C^2), where m and n are the lengths of strings a and b respectively, and C is the size of the character set. In this problem, C = 26.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Prefix Sums for Strictly Less Condition | Time Complexity: O(n + m), where n is the length of a and m is the length of b, since we loop over each string to build frequency counts and prefix sums. Space Complexity: O(1), since the space used is constant and not dependent on the input size. |
| Direct Count and Compare | Time Complexity: O(n + m). Space Complexity: O(1). |
| Counting + Enumeration | ā |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Count and Compare | O(n + 26) | O(26) | Simple implementation when using frequency arrays to evaluate all conditions directly. |
| Prefix Sums for Strictly Less Condition | O(n + 26) | O(26) | Preferred approach when efficiently evaluating lexicographic split points using cumulative counts. |
Video Solution
LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions ā¢ Happy Coding ā¢ 1,314 views views
Watch 7 more video solutions āFrequently Asked Questions
Is Change Minimum Characters to Satisfy One of Three Conditions easy or hard?
Change Minimum Characters to Satisfy One of Three Conditions Python/Java solution
How to solve Change Minimum Characters to Satisfy One of Three Conditions in O(n)?
What is the best approach for Change Minimum Characters to Satisfy One of Three Conditions?
Is Change Minimum Characters to Satisfy One of Three Conditions asked at Google/Amazon/Meta?
What data structure is used in Change Minimum Characters to Satisfy One of Three Conditions?
What is the time complexity of Change Minimum Characters to Satisfy One of Three Conditions?
Ready to solve this problem?
Practice Change Minimum Characters to Satisfy One of Three Conditions with our built-in code editor and test cases.
Practice on FleetCode