Welcome to Subscribe On Youtube

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

  • 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;
        }
    }
}


  • 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 ''

All Problems

All Solutions