Skip to content

3720. Lexicographically Smallest Permutation Greater Than Target

Description

You are given two strings s and target, both having length n, consisting of lowercase English letters.

Return the lexicographically smallest permutation of s that is strictly greater than target. If no permutation of s is lexicographically strictly greater than target, return an empty string.

A string a is lexicographically strictly greater than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b.

Β 

Example 1:

Input: s = "abc", target = "bba"

Output: "bca"

Explanation:

  • The permutations of s (in lexicographical order) are "abc", "acb", "bac", "bca", "cab", and "cba".
  • The lexicographically smallest permutation that is strictly greater than target is "bca".

Example 2:

Input: s = "leet", target = "code"

Output: "eelt"

Explanation:

  • The permutations of s (in lexicographical order) are "eelt", "eetl", "elet", "elte", "etel", "etle", "leet", "lete", "ltee", "teel", "tele", and "tlee".
  • The lexicographically smallest permutation that is strictly greater than target is "eelt".

Example 3:

Input: s = "baba", target = "bbaa"

Output: ""

Explanation:

  • The permutations of s (in lexicographical order) are "aabb", "abab", "abba", "baab", "baba", and "bbaa".
  • None of them is lexicographically strictly greater than target. Therefore, the answer is "".

Β 

Constraints:

  • 1 <= s.length == target.length <= 300
  • s and target consist of only lowercase English letters.

Solutions

Solution 1: Greedy + Backtracking

To be strictly greater than \(\textit{target}\), the answer must look like this: it matches some prefix of \(\textit{target}\) exactly, places a character greater than the corresponding character of \(\textit{target}\) at the next position, and arranges the remaining characters in ascending order. The longer this common prefix is, the smaller the resulting permutation, so we want the common prefix to be as long as possible.

We first count the occurrences of every character of \(s\) in \(\textit{cnt}\), then match \(\textit{target}\) from left to right as far as we can: as long as the current character is still available we take it and append it to the answer, stopping once some character runs out. This yields the longest common prefix.

Next we walk back from the end of that prefix, trying each position \(i\) as the place where the answer diverges: we put the smallest still available character greater than \(\textit{target}[i]\) at position \(i\), and if that succeeds we append the remaining characters in ascending order and return. Otherwise we give \(\textit{target}[i - 1]\) back to \(\textit{cnt}\) and try an earlier position. Note that when \(\textit{target}\) itself is a permutation of \(s\), no character can be placed at position \(n\), so we have to start backtracking from the last position because the answer must be strictly greater. If every position fails, no such permutation exists and we return an empty string.

The time complexity is \(O(n \times |\Sigma|)\), and the space complexity is \(O(n + |\Sigma|)\). Here, \(n\) is the length of the string \(s\), and \(|\Sigma| = 26\) is the size of the character set.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def lexGreaterPermutation(self, s: str, target: str) -> str:
        cnt = Counter(s)
        n = len(target)
        ans = []
        for c in target:
            if cnt[c] == 0:
                break
            cnt[c] -= 1
            ans.append(c)
        for i in range(len(ans), -1, -1):
            if i < n:
                for c in ascii_lowercase:
                    if c > target[i] and cnt[c] > 0:
                        cnt[c] -= 1
                        rest = ''.join(x * cnt[x] for x in ascii_lowercase)
                        return ''.join(ans[:i]) + c + rest
            if i > 0:
                cnt[ans[i - 1]] += 1
        return ''

1


1


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
32
33
34
35
36
37
38
39
40
41
42
43
44
impl Solution {
    pub fn lex_greater_permutation(s: String, target: String) -> String {
        let mut permutation = s.into_bytes();
        let target_bytes = target.as_bytes();
        let mut letter_counts = [0usize; 26];
        for &byte in &permutation {
            letter_counts[(byte - b'a') as usize] += 1;
        }
        let mut prefix_length = 0;
        while prefix_length < target_bytes.len() {
            let target_letter = (target_bytes[prefix_length] - b'a') as usize;
            if letter_counts[target_letter] == 0 {
                break;
            }
            permutation[prefix_length] = target_bytes[prefix_length];
            letter_counts[target_letter] -= 1;
            prefix_length += 1;
        }
        loop {
            if prefix_length < target_bytes.len() {
                let next_letter = (target_bytes[prefix_length] - b'a') as usize + 1;
                if let Some(replacement_letter) =
                    (next_letter..26).find(|&letter| letter_counts[letter] > 0)
                {
                    permutation[prefix_length] = b'a' + replacement_letter as u8;
                    letter_counts[replacement_letter] -= 1;
                    let mut write_index = prefix_length + 1;
                    for (letter, &count) in letter_counts.iter().enumerate() {
                        for _ in 0..count {
                            permutation[write_index] = b'a' + letter as u8;
                            write_index += 1;
                        }
                    }
                    return String::from_utf8(permutation).unwrap();
                }
            }
            if prefix_length == 0 {
                return String::new();
            }
            prefix_length -= 1;
            letter_counts[(target_bytes[prefix_length] - b'a') as usize] += 1;
        }
    }
}

Comments