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

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

✓ Brute Force - Try All Boundaries

⏱️ Time: O(26 × (n + m)) Space: O(1)

For each of 26 possible split characters, calculate the cost of making all characters in string a less than the split and all characters in string b greater than or equal to the split (and vice versa). Also calculate the cost of making both strings identical.

Frequency Count with Prefix Optimization

⏱️ Time: O(n + m + 26) Space: O(1)

Count the frequency of each character in both strings, then use prefix sums to efficiently calculate the cost of each possible boundary split. This avoids recalculating costs for each boundary character.

Single Pass Optimized

⏱️ Time: O(n + m) Space: O(1)

Count character frequencies in both strings, then in a single pass through the alphabet, calculate the minimum operations for all three conditions simultaneously. This eliminates redundant calculations.

Brute Force - Try All Boundaries — Algorithm Steps

Count frequency of each character in both strings
Try each character 'a' to 'z' as boundary
Calculate operations for all three conditions
Return minimum across all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Boundary

Test each character a-z as split point

Count Operations

Calculate changes needed for each condition

Find Minimum

Return the smallest operation count

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);
    int minOps = INT_MAX;
    
    // Try all possible boundary characters
    for (int boundary = 0; boundary < 26; boundary++) {
        char boundaryChar = 'a' + boundary;
        
        // Condition 1: all chars in a < boundary, all chars in b >= boundary
        int ops1 = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] >= boundaryChar) ops1++;
        }
        for (int i = 0; i < m; i++) {
            if (b[i] < boundaryChar) ops1++;
        }
        
        // Condition 2: all chars in b < boundary, all chars in a >= boundary
        int ops2 = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] < boundaryChar) ops2++;
        }
        for (int i = 0; i < m; i++) {
            if (b[i] >= boundaryChar) ops2++;
        }
        
        if (ops1 < minOps) minOps = ops1;
        if (ops2 < minOps) minOps = ops2;
    }
    
    // Condition 3: make both strings identical
    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']++;
    }
    
    for (int targetChar = 0; targetChar < 26; targetChar++) {
        int ops3 = (n - freqA[targetChar]) + (m - freqB[targetChar]);
        if (ops3 < minOps) minOps = ops3;
    }
    
    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(26 × (n + m))

26 possible boundaries, each requiring O(n + m) to calculate costs

✓ Linear Growth

Space Complexity

O(1)

Only using constant space for frequency arrays and 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

Change Minimum Characters to Satisfy One of Three Conditions - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Boundaries — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler