Formatted question description: https://leetcode.ca/all/1737.html

1737. Change Minimum Characters to Satisfy One of Three Conditions

Level

Medium

Description

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^5
a and b consist only of lowercase letters.

Solution

For the first two conditions, calculate the number of occurrences of each letter in each of the strings a and b respectively, and calculate the prefix sums and the suffix sums respectively. Then loop over the number of occurrences. For each i from 0 to 24, calculate the number of operations to change letters in a to letters in indices 0 to i and change letters in b to letters in indices i + 1 to 25, and calculate the number of operations to change letters in b to letters in indices 0 to i and change letters in a to letters in indices i + 1 to 25. Maintain the minimum number of operations during the process, which is the minimum number of operations for conditions 1 and 2.

For condition 3, obtain the maximum occurrence of letters in a and b respectively, and the remaining letters need to be changed to such a letter for each string.

Finally, return the minimum number of operations among three conditions.

class Solution {
    public int minCharacters(String a, String b) {
        int[] aCounts = new int[26];
        int[] bCounts = new int[26];
        int aMaxCount = 0, bMaxCount = 0;
        int aLength = a.length(), bLength = b.length();
        for (int i = 0; i < aLength; i++) {
            char c = a.charAt(i);
            aCounts[c - 'a']++;
            aMaxCount = Math.max(aMaxCount, aCounts[c - 'a']);
        }
        for (int i = 0; i < bLength; i++) {
            char c = b.charAt(i);
            bCounts[c - 'a']++;
            bMaxCount = Math.max(bMaxCount, bCounts[c - 'a']);
        }
        int[] aCountsPrefix = new int[26];
        int[] aCountsSuffix = new int[26];
        int[] bCountsPrefix = new int[26];
        int[] bCountsSuffix = new int[26];
        aCountsPrefix[0] = aCounts[0];
        bCountsPrefix[0] = bCounts[0];
        for (int i = 1; i < 26; i++) {
            aCountsPrefix[i] = aCountsPrefix[i - 1] + aCounts[i];
            bCountsPrefix[i] = bCountsPrefix[i - 1] + bCounts[i];
        }
        aCountsSuffix[25] = aCounts[25];
        bCountsSuffix[25] = bCounts[25];
        for (int i = 24; i >= 0; i--) {
            aCountsSuffix[i] = aCountsSuffix[i + 1] + aCounts[i];
            bCountsSuffix[i] = bCountsSuffix[i + 1] + bCounts[i];
        }
        int op1 = Integer.MAX_VALUE, op2 = Integer.MAX_VALUE;
        for (int i = 0; i < 25; i++) {
            int curOp1 = aLength - aCountsPrefix[i] + bLength - bCountsSuffix[i + 1];
            int curOp2 = aLength - aCountsSuffix[i + 1] + bLength - bCountsPrefix[i];
            op1 = Math.min(op1, curOp1);
            op2 = Math.min(op2, curOp2);
        }
        int op3 = aLength - aMaxCount + bLength - bMaxCount;
        return Math.min(Math.min(op1, op2), op3);
    }
}

############

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

// OJ: https://leetcode.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/
// Time: O(A + B)
// Space: O(1)
class Solution {
public:
    int minCharacters(string a, string b) {
        array<int, 26> ca = {}, cb = {};
        for (char c : a) ca[c - 'a']++;
        for (char c : b) cb[c - 'a']++;
        int M = a.size(), N = b.size(), op1 = M, op2 = N, ans = INT_MAX;
        for (int i = 0; i < 26; ++i) {
            op1 += cb[i] - ca[i];
            op2 += ca[i] - cb[i];
            if (i < 25) ans = min({ ans, op1, op2 });
            ans = min(ans, M + N - ca[i] - cb[i]);
        }
        return ans;
    }
};

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

############

# 1737. Change Minimum Characters to Satisfy One of Three Conditions
# https://leetcode.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/

class Solution:
    def minCharacters(self, A: str, B: str):
        countA = Counter(ord(c) - ord('a') for c in A)
        countB = Counter(ord(c) - ord('a') for c in B)
    
        def operation1(a, b):
            # a < i, b >= i
            res = float('inf')
            for i in range(1,26):
                count = sum(a[j] for j in range(i))
                count += sum(b[j] for j in range(i, 26))
                
                res = min(res, count)
                
            return res
        
        def operation3(a, b):
            res = float('-inf')

            for i in range(26):
                res = max(res, a[i] + b[i])
            
            return len(A) + len(B) - res
        
        return min(operation1(countA, countB), operation1(countB, countA), operation3(countA, countB))
                
        

func minCharacters(a string, b string) int {
	cnt1 := [26]int{}
	cnt2 := [26]int{}
	for _, c := range a {
		cnt1[c-'a']++
	}
	for _, c := range b {
		cnt2[c-'a']++
	}
	m, n := len(a), len(b)
	ans := m + n
	for i := 0; i < 26; i++ {
		ans = min(ans, m+n-cnt1[i]-cnt2[i])
	}
	f := func(cnt1, cnt2 [26]int) {
		for i := 1; i < 26; i++ {
			t := 0
			for j := i; j < 26; j++ {
				t += cnt1[j]
			}
			for j := 0; j < i; j++ {
				t += cnt2[j]
			}
			ans = min(ans, t)
		}
	}
	f(cnt1, cnt2)
	f(cnt2, cnt1)
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

function minCharacters(a: string, b: string): number {
    const m = a.length,
        n = b.length;
    let count1 = new Array(26).fill(0);
    let count2 = new Array(26).fill(0);
    const base = 'a'.charCodeAt(0);

    for (let char of a) {
        count1[char.charCodeAt(0) - base]++;
    }
    for (let char of b) {
        count2[char.charCodeAt(0) - base]++;
    }

    let pre1 = 0,
        pre2 = 0;
    let ans = m + n;
    for (let i = 0; i < 25; i++) {
        pre1 += count1[i];
        pre2 += count2[i];
        // case1， case2， case3
        ans = Math.min(
            ans,
            m - pre1 + pre2,
            pre1 + n - pre2,
            m + n - count1[i] - count2[i],
        );
    }
    ans = Math.min(ans, m + n - count1[25] - count2[25]);

    return ans;
}

1737 - Change Minimum Characters to Satisfy One of Three Conditions

1737. Change Minimum Characters to Satisfy One of Three Conditions

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1737. Change Minimum Characters to Satisfy One of Three Conditions

Level

Description

Solution

All Problems

All Solutions