Lexicographically Largest String After Pair Transformations - Solution & Explanation

Problem Overview: You are given a string of lowercase letters and a list of pair transformations, where each transformation replaces one character with another. You can apply any subset of these transformations to the string, but each transformation can be used at most once. The goal is to produce the lexicographically largest possible string after applying some (possibly zero) transformations.

Approach 1: Brute Force (O(2^m * n) Time, O(n) Space)

Enumerate every subset of the given transformations using bitmasking. For each subset, apply the transformations to the string in some order (the order matters because transformations can chain). After applying, compare the resulting string with the current best lexicographically. This approach is exponential in the number of transformations and only works for very small inputs. It demonstrates the naive way to explore all possibilities but is impractical for larger constraints.

Approach 2: Greedy with Character Frequency (O(n + m) Time, O(1) Space)

The key insight is that lexicographic order is determined by the earliest position where two strings differ. To maximize the string, you want to make the earliest possible characters as large as possible. Since each transformation can be used at most once, you can process the string from left to right. For each character, check if there is any transformation that maps it to a larger character. If yes, apply the transformation that yields the largest possible character. Because transformations are independent and each is used once, this greedy choice is optimal. Use a frequency array of size 26 to track which transformations are available, and update it as you apply them. This runs in linear time with respect to the string length plus the number of transformations.

Approach 3: Optimized Greedy with Precomputed Best Mapping (O(n + m) Time, O(1) Space)

Precompute for each character the maximum character it can become using any single transformation. Then iterate through the string and replace each character with its precomputed maximum if that maximum is greater than the original character. This avoids repeatedly checking all transformations for each character. The space complexity remains constant because you only store a 26-element array. This is the cleanest and most efficient solution, and it is what interviewers expect.

Recommended for interviews: The greedy approach is the standard solution. Start by explaining the brute force to show you understand the problem space, then pivot to the greedy insight: because transformations are independent and you want the earliest difference to be as large as possible, processing left-to-right with a frequency map or precomputed best mapping yields the optimal answer in linear time. This demonstrates both problem-solving skill and knowledge of greedy algorithms and string manipulation.