Welcome to Subscribe On Youtube

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

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


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

All Problems

All Solutions