Change Minimum Characters to Satisfy One of Three Conditions - Video Solutions

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.