Skip to content

3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

Description

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

Return the lexicographically smallest string that is both a palindromic permutation of s and strictly greater than target. If no such permutation exists, return an empty string.

 

Example 1:

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

Output: "baab"

Explanation:

  • The palindromic permutations of s (in lexicographical order) are "abba" and "baab".
  • The lexicographically smallest permutation that is strictly greater than target is "baab".

Example 2:

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

Output: ""

Explanation:

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

Example 3:

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

Output: ""

Explanation:

s has no palindromic permutations. Therefore, the answer is "".

Example 4:

Input: s = "aac", target = "abb"

Output: "aca"

Explanation:

  • The only palindromic permutation of s is "aca".
  • "aca" is strictly greater than target. Therefore, the answer is "aca".

 

Constraints:

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

Solutions

Solution 1

Thinking

A palindromic permutation is determined by its left half and at most one odd center; more than one odd frequency is impossible. We want the smallest palindrome strictly larger than \(\textit{target}\), so the left half is built like the next permutation: match the first half of \(\textit{target}\) as far as possible, raise the first feasible position, and mirror the left half to the right.

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
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
class Solution {
public:
    string buildPalindrome(string left, char middle, int n) {
        string right = left;
        reverse(right.begin(), right.end());
        if (n % 2 == 1) {
            return left + string(1, middle) + right;
        }
        return left + right;
    }

    string lexPalindromicPermutation(string s, string target) {
        int n = s.size();
        vector<int> freq(26, 0);
        for (char c : s) {
            freq[c - 'a']++;
        }

        int oddCount = 0;
        char middle = 0;
        for (int i = 0; i < 26; i++) {
            if (freq[i] % 2 == 1) {
                oddCount++;
                middle = char('a' + i);
            }
        }
        if (oddCount > 1) {
            return "";
        }

        vector<int> halfFreq(26, 0);
        for (int i = 0; i < 26; i++) {
            halfFreq[i] = freq[i] / 2;
        }

        int halfLen = n / 2;
        string targetHalf = target.substr(0, halfLen);
        vector<int> remaining = halfFreq;
        string prefix = "";
        int matched = 0;
        for (int i = 0; i < halfLen; i++) {
            int x = targetHalf[i] - 'a';
            if (remaining[x] == 0) {
                break;
            }
            prefix += targetHalf[i];
            remaining[x]--;
            matched++;
        }

        if (matched == halfLen) {
            string candidate = buildPalindrome(prefix, middle, n);
            if (candidate > target) {
                return candidate;
            }
        }

        int lastPosition = matched == halfLen ? halfLen - 1 : matched;
        for (int pos = lastPosition; pos >= 0; pos--) {
            vector<int> rem = halfFreq;
            bool validPrefix = true;
            for (int i = 0; i < pos; i++) {
                int x = targetHalf[i] - 'a';
                if (rem[x] == 0) {
                    validPrefix = false;
                    break;
                }
                rem[x]--;
            }
            if (!validPrefix) {
                continue;
            }

            int targetChar = targetHalf[pos] - 'a';
            for (int c = targetChar + 1; c < 26; c++) {
                if (rem[c] == 0) {
                    continue;
                }
                string left = targetHalf.substr(0, pos);
                left += char('a' + c);
                rem[c]--;
                for (int x = 0; x < 26; x++) {
                    while (rem[x] > 0) {
                        left += char('a' + x);
                        rem[x]--;
                    }
                }
                string candidate = buildPalindrome(left, middle, n);
                if (candidate > target) {
                    return candidate;
                }
                rem = halfFreq;
                for (int i = 0; i < pos; i++) {
                    rem[targetHalf[i] - 'a']--;
                }
            }
        }

        return "";
    }
};

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
impl Solution {
    pub fn lex_palindromic_permutation(s: String, target: String) -> String {
        let mut freq = [0usize; 26];
        s.bytes().for_each(|ch| freq[(ch - b'a') as usize] += 1);
        if freq.iter().filter(|&&cnt| cnt & 1 != 0).count() > 1 {
            return String::new();
        }
        let mid = freq.iter().position(|cnt| cnt & 1 != 0);
        freq.iter_mut().for_each(|cnt| *cnt /= 2);
        let mut ans = s.into_bytes();
        let tgt = target.as_bytes();
        let half = ans.len() / 2;
        let make = |buf: &mut [u8]| {
            if let Some(ch) = mid {
                buf[half] = b'a' + ch as u8;
            }
            let len = buf.len();
            for idx in 0..half {
                let ch = buf[idx];
                buf[len - 1 - idx] = ch;
            }
        };
        let mut pos = 0;
        while pos < half {
            let ch = (tgt[pos] - b'a') as usize;
            if freq[ch] == 0 {
                break;
            }
            ans[pos] = tgt[pos];
            freq[ch] -= 1;
            pos += 1;
        }
        if pos == half {
            make(&mut ans);
            if ans.as_slice() > tgt {
                return String::from_utf8(ans).unwrap();
            }
        }
        loop {
            if pos < half {
                let min = (tgt[pos] - b'a' + 1) as usize;
                if let Some(ch) = (min..26).find(|&ch| freq[ch] != 0) {
                    ans[pos] = b'a' + ch as u8;
                    freq[ch] -= 1;
                    let mut dst = pos + 1;
                    for (ch, &cnt) in freq.iter().enumerate() {
                        for off in 0..cnt {
                            ans[dst + off] = b'a' + ch as u8;
                        }
                        dst += cnt;
                    }
                    make(&mut ans);
                    return String::from_utf8(ans).unwrap();
                }
            }
            if pos == 0 {
                return String::new();
            }
            pos -= 1;
            freq[(tgt[pos] - b'a') as usize] += 1;
        }
    }
}

Comments