Change Minimum Characters to Satisfy One of Three Conditions

Change Minimum Characters to Satisfy One of Three Conditions - 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.

Input & Output

Example 1 — Basic Case

$ Input: a = "aba", b = "caa"

› Output: 2

💡 Note: We can make a < b by changing 'a' to 'b' in string a (1 op) and 'a' to 'c' in string b (1 op), giving us "bbb" < "ccc". Total: 2 operations.

Example 2 — Make Identical

$ Input: a = "dabadd", b = "cda"

› Output: 3

💡 Note: Best option is to make both strings contain only 'd': change 'a','b','a' in first string (3 ops) and 'c','a' in second string (2 ops), but we can make both 'a' with only 3 total operations.

Example 3 — Already Ordered

$ Input: a = "aaa", b = "bbb"

› Output: 0

💡 Note: String a already has all characters less than all characters in string b, so no operations needed.

Constraints

1 ≤ a.length, b.length ≤ 10⁵
a and b consist only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings a="aba", b="caa" with mixed character order

Process

Try 3 conditions: a<b, b<a, or both identical

Output

Minimum operations needed: 2

Key Takeaway

🎯 Key Insight: Find the optimal boundary or target character that minimizes changes across all three possible conditions

Asked in

G Google 15 f Facebook 12 M Microsoft 8

The key insight is to recognize that we need to find the optimal boundary character or target character that minimizes total operations across all three conditions. The best approach uses frequency counting with single pass optimization to calculate all possibilities efficiently. Time: O(n + m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Optimized	O(n + m)	O(1)	Calculate all conditions in one pass through frequency arrays
Frequency Count with Prefix Optimization	O(n + m + 26)	O(1)	Count character frequencies and use prefix sums to efficiently calculate operations
Brute Force - Try All Boundaries	O(26 × (n + m))	O(1)	Try every possible split character and calculate operations for each condition

Single Pass Optimized — Algorithm Steps

Count frequency of each character in both strings
In single pass, track cumulative costs for boundaries
Calculate identical string costs for each character
Return minimum across all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Count frequencies and set cumulative trackers

Single Pass

For each character, calculate all 3 condition costs

Track Minimum

Keep running minimum and update cumulative counts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(char* a, char* b) {
    int n = strlen(a), m = strlen(b);
    
    // Count frequencies
    int freqA[26] = {0}, freqB[26] = {0};
    
    for (int i = 0; i < n; i++) {
        freqA[a[i] - 'a']++;
    }
    for (int i = 0; i < m; i++) {
        freqB[b[i] - 'a']++;
    }
    
    int minOps = INT_MAX;
    
    // Track cumulative counts for boundary conditions
    int cumA = 0;  // chars in a that are < current boundary
    int cumB = 0;  // chars in b that are < current boundary
    
    for (int i = 0; i < 26; i++) {
        // Condition 1: all a < boundary, all b >= boundary
        int ops1 = (n - cumA) + cumB;
        
        // Condition 2: all b < boundary, all a >= boundary
        int ops2 = cumA + (m - cumB);
        
        // Condition 3: make both strings use only character i
        int ops3 = (n - freqA[i]) + (m - freqB[i]);
        
        if (ops1 < minOps) minOps = ops1;
        if (ops2 < minOps) minOps = ops2;
        if (ops3 < minOps) minOps = ops3;
        
        // Update cumulative counts
        cumA += freqA[i];
        cumB += freqB[i];
    }
    
    return minOps;
}

int main() {
    char a[100001], b[100001];
    fgets(a, sizeof(a), stdin);
    fgets(b, sizeof(b), stdin);
    
    // Remove newlines
    a[strcspn(a, "\n")] = 0;
    b[strcspn(b, "\n")] = 0;
    
    int result = solution(a, b);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Single pass to count frequencies, O(26) to process alphabet which is constant

✓ Linear Growth

Space Complexity

O(1)

Only frequency arrays of fixed size 26 and a few variables

✓ Linear Space

55.4K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Optimized — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler