# 1737. Change Minimum Characters to Satisfy One of Three Conditions

• Time: $O(|\texttt{a}| + |\texttt{b}|)$
• Space: $O(128) = O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public: int minCharacters(string a, string b) { const int m = a.length(); const int n = b.length(); vector countA(128); vector countB(128); for (const char c : a) ++countA[c]; for (const char c : b) ++countB[c]; int ans = INT_MAX; int prevA = 0; // # of chars in a <= c int prevB = 0; // # of chars in b <= c for (char c = 'a'; c <= 'z'; ++c) { // Condition 3 ans = min(ans, m + n - countA[c] - countB[c]); // Condition 1 and 2 if (c > 'a') ans = min({ans, m - prevA + prevB, n - prevB + prevA}); prevA += countA[c]; prevB += countB[c]; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public int minCharacters(String a, String b) { final int m = a.length(); final int n = b.length(); int[] countA = new int[128]; int[] countB = new int[128]; for (final char c : a.toCharArray()) ++countA[c]; for (final char c : b.toCharArray()) ++countB[c]; int ans = Integer.MAX_VALUE; int prevA = 0; // # of chars in a <= c int prevB = 0; // # of chars in b <= c for (char c = 'a'; c <= 'z'; ++c) { // Condition 3 ans = Math.min(ans, m + n - countA[c] - countB[c]); // Condition 1 and 2 if (c > 'a') ans = Math.min(ans, Math.min(m - prevA + prevB, n - prevB + prevA)); prevA += countA[c]; prevB += countB[c]; } return ans; } }