4036. Lexicographically Largest String After Pair Transformations

Description

You are given an integer array nums.

For each integer x in nums, start with a string consisting of exactly x lowercase 'a' characters.

You may perform the following operation any number of times (including zero):

• Choose two adjacent equal letters and replace them with the next letter in the alphabet.

For example, "aa" can be replaced with "b", and "bb" can be replaced with "c". The pair "zz" cannot be replaced.

For each x, determine the lexicographically largest string that can be obtained.

Return an array of strings where the ith string is the answer for nums[i].

A string a is lexicographically larger than a string b if, at the first position where they differ, a contains a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters are equal, the longer string is lexicographically larger.

Example 1:

Example 2:

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 108

Solutions

Solution 1: Greedy + Binary Decomposition

Since two adjacent identical letters merge into the next letter of the alphabet, the letter \(\texttt{'a'} + j\) is equivalent to \(2^j\) copies of \(\texttt{'a'}\). In other words, the strings reachable from \(x\) copies of \(\texttt{'a'}\) are exactly those whose letter weights sum to \(x\).

To maximize the lexicographical order, we greedily use the heaviest letters first. The largest letter is \(\texttt{'z'}\) with weight \(2^{25}\), so we iterate \(j\) from \(25\) down to \(0\), append \(t = \left\lfloor x / 2^j \right\rfloor\) copies of the letter \(\texttt{'a'} + j\) to the answer, and set \(x \leftarrow x \bmod 2^j\).

Note that \(t \in \{0, 1\}\) whenever \(j \lt 25\), so only \(\texttt{'z'}\) can appear consecutively in the answer, and \(\texttt{"zz"}\) cannot be merged any further. Therefore the resulting string is valid and lexicographically largest.

The time complexity is \(O(n \times \log M)\), and the space complexity is \(O(\log M)\). Here, \(n\) is the length of the array \(\textit{nums}\), and \(M\) is the maximum value in the array \(\textit{nums}\). The space for the answer is not counted.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def largestString(self, nums: List[int]) -> List[str]:
        ans = []
        for x in nums:
            s = []
            for j in range(25, -1, -1):
                t = x >> j
                s.append(chr(ord('a') + j) * t)
                x &= (1 << j) - 1
            ans.append(''.join(s))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public String[] largestString(int[] nums) {
        int n = nums.length;
        String[] ans = new String[n];
        for (int k = 0; k < n; ++k) {
            int x = nums[k];
            StringBuilder s = new StringBuilder();
            for (int j = 25; j >= 0; --j) {
                for (int t = x >> j; t > 0; --t) {
                    s.append((char) ('a' + j));
                }
                x &= (1 << j) - 1;
            }
            ans[k] = s.toString();
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<string> largestString(vector<int>& nums) {
        vector<string> ans;
        ans.reserve(nums.size());
        for (int x : nums) {
            string s;
            for (int j = 25; j >= 0; --j) {
                for (int t = x >> j; t > 0; --t) {
                    s.push_back('a' + j);
                }
                x &= (1 << j) - 1;
            }
            ans.push_back(s);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func largestString(nums []int) []string {
    ans := make([]string, 0, len(nums))
    for _, x := range nums {
        s := []byte{}
        for j := 25; j >= 0; j-- {
            for t := x >> j; t > 0; t-- {
                s = append(s, byte('a'+j))
            }
            x &= (1 << j) - 1
        }
        ans = append(ans, string(s))
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function largestString(nums: number[]): string[] {
    const ans: string[] = [];
    for (let x of nums) {
        const s: string[] = [];
        for (let j = 25; j >= 0; --j) {
            const t = x >> j;
            s.push(String.fromCharCode(97 + j).repeat(t));
            x &= (1 << j) - 1;
        }
        ans.push(s.join(''));
    }
    return ans;
}

Comments