LeetCode 3734 - Lexicographically Smallest Palindromic Permutation Greater Than Target

LeetCode Problem 3734

Difficulty: 🔴 Hard
Topics: Two Pointers, String, Enumeration

Solution

Problem Understanding

We are given two strings, s and target, of the same length n.

The goal is to rearrange the characters of s into a palindrome and then choose, among all possible palindromic permutations, the lexicographically smallest one that is strictly greater than target.

A string a is lexicographically greater than a string b if, at the first position where they differ, a contains a larger character.

The key restriction is that the final string must be both:

1. A permutation of the characters in s.
2. A palindrome.

If no palindromic permutation exists, or if every palindromic permutation is less than or equal to target, we return an empty string.

The constraints are important:

• n ≤ 300, which is small enough for an O(n²) solution.
• Characters are limited to lowercase English letters, so there are only 26 distinct character types.

A palindrome can only exist if at most one character has an odd frequency. If two or more characters occur an odd number of times, no palindromic permutation is possible.

Some important edge cases are:

• s has no palindromic permutation.
• Only one palindromic permutation exists.
• The only palindromic permutation is equal to target.
• Every palindromic permutation is smaller than target.
• The answer differs from target very late in the string, requiring careful lexicographic construction.

Approaches

Brute Force

A brute force solution would generate every permutation of s, filter out the non-palindromes, sort the remaining palindromes, and then find the first one greater than target.

This is correct because it explicitly examines all possibilities.

Unfortunately, even for moderate string lengths, the number of permutations grows as n!, making this completely infeasible. With n up to 300, brute force is impossible.

Key Insight

A palindrome is completely determined by:

• Its left half.
• Its middle character, if the length is odd.

Suppose the character counts in s are known.

For every character with count cnt[c], exactly cnt[c] // 2 copies must appear in the left half. The right half is then forced by symmetry.

Therefore, instead of arranging all n positions, we only need to arrange the left half.

The next observation is a standard lexicographic construction idea:

When building the left half from left to right, we always try the smallest possible character first.

For a candidate choice, we ask:

Is there at least one completion of the remaining positions that produces a palindrome greater than target?

If yes, we keep that character. Otherwise, we try the next larger character.

To answer the feasibility question, we construct the lexicographically largest palindrome obtainable from the current prefix. If even this largest possible completion is not greater than target, then no completion can work.

This allows a greedy construction of the answer.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n!)	Enumerates all permutations
Optimal	O(26 · n²) = O(n²)	O(n)	Greedy construction with feasibility checks

Algorithm Walkthrough

1. Count the frequency of every character in s.
2. Check whether a palindromic permutation is possible.

• Count how many characters have odd frequency.
• If more than one character has odd frequency, return "".

3. Determine the palindrome structure.

• For each character, store count // 2 copies in the left half inventory.
• If n is odd, identify the unique middle character.

4. Build the left half greedily from left to right.

5. For each position in the left half:

6. Try every available character from 'a' to 'z'.

7. Temporarily place that character.

8. Check whether some valid completion can still produce a palindrome greater than target.

9. To perform the feasibility check:

10. Fix the current prefix.

11. Fill all remaining left-half positions with the largest available characters in descending order.

12. Construct the corresponding palindrome.

13. Compare it with target.

14. If this maximum possible palindrome is still not greater than target, then no completion works, so undo the choice and try the next character.

15. Otherwise, keep the character permanently and move to the next position.

16. After all left-half positions are chosen, construct the final palindrome:

• left half
• middle character (if any)
• reversed left half

10. Return the palindrome if it is greater than target, otherwise return "".

Why it works

At every position we choose the smallest character that still allows some valid solution. If a smaller character cannot lead to any palindrome greater than target, then choosing it would make success impossible. Therefore the first feasible character is always part of the lexicographically smallest valid answer.

The feasibility test is correct because it examines the largest possible completion. If even the largest completion fails to exceed target, then no smaller completion can succeed.

Python Solution

class Solution:
    def lexPalindromicPermutation(self, s: str, target: str) -> str:
        counts = [0] * 26
        for ch in s:
            counts[ord(ch) - ord('a')] += 1

        odd_count = sum(c % 2 for c in counts)
        if odd_count > 1:
            return ""

        middle = ""
        if len(s) % 2 == 1:
            for i in range(26):
                if counts[i] % 2 == 1:
                    middle = chr(ord('a') + i)
                    break

        half_counts = [c // 2 for c in counts]
        half_len = len(s) // 2

        prefix = []

        def feasible() -> bool:
            left = "".join(prefix)

            remaining_desc = []
            for i in range(25, -1, -1):
                if half_counts[i]:
                    remaining_desc.append(
                        chr(ord('a') + i) * half_counts[i]
                    )

            left += "".join(remaining_desc)

            palindrome = left + middle + left[::-1]
            return palindrome > target

        for _ in range(half_len):
            chosen = False

            for char_idx in range(26):
                if half_counts[char_idx] == 0:
                    continue

                half_counts[char_idx] -= 1
                prefix.append(chr(ord('a') + char_idx))

                if feasible():
                    chosen = True
                    break

                prefix.pop()
                half_counts[char_idx] += 1

            if not chosen:
                return ""

        left_half = "".join(prefix)
        answer = left_half + middle + left_half[::-1]

        return answer if answer > target else ""

The implementation begins by counting character frequencies and verifying that a palindrome can exist. The odd-frequency character, if one exists, becomes the middle character.

The array half_counts stores the inventory of characters available for the left half. Since the right half is forced by symmetry, this completely describes the remaining choices.

The main loop greedily builds the left half. For each position, characters are tested in ascending order. A character is accepted only if the feasibility test succeeds.

The feasibility test constructs the lexicographically largest palindrome obtainable from the current prefix. It does this by placing all remaining characters in descending order within the left half. If this largest completion is greater than target, then at least one valid completion exists.

After all positions are fixed, the final palindrome is assembled and returned.

Go Solution

func lexPalindromicPermutation(s string, target string) string {
	counts := make([]int, 26)

	for _, ch := range s {
		counts[ch-'a']++
	}

	oddCount := 0
	for _, c := range counts {
		if c%2 == 1 {
			oddCount++
		}
	}

	if oddCount > 1 {
		return ""
	}

	middle := ""
	if len(s)%2 == 1 {
		for i := 0; i < 26; i++ {
			if counts[i]%2 == 1 {
				middle = string(rune('a' + i))
				break
			}
		}
	}

	halfCounts := make([]int, 26)
	for i := 0; i < 26; i++ {
		halfCounts[i] = counts[i] / 2
	}

	halfLen := len(s) / 2
	prefix := make([]byte, 0, halfLen)

	feasible := func() bool {
		left := make([]byte, 0, halfLen)

		left = append(left, prefix...)

		for i := 25; i >= 0; i-- {
			for k := 0; k < halfCounts[i]; k++ {
				left = append(left, byte('a'+i))
			}
		}

		leftStr := string(left)

		palindrome := leftStr + middle

		for i := len(leftStr) - 1; i >= 0; i-- {
			palindrome += string(leftStr[i])
		}

		return palindrome > target
	}

	for pos := 0; pos < halfLen; pos++ {
		chosen := false

		for c := 0; c < 26; c++ {
			if halfCounts[c] == 0 {
				continue
			}

			halfCounts[c]--
			prefix = append(prefix, byte('a'+c))

			if feasible() {
				chosen = true
				break
			}

			prefix = prefix[:len(prefix)-1]
			halfCounts[c]++
		}

		if !chosen {
			return ""
		}
	}

	leftHalf := string(prefix)

	answer := leftHalf + middle
	for i := len(leftHalf) - 1; i >= 0; i-- {
		answer += string(leftHalf[i])
	}

	if answer > target {
		return answer
	}

	return ""
}

The Go implementation follows exactly the same logic as the Python version.

The primary language-specific difference is that character manipulation is performed through byte slices rather than Python strings. The frequency arrays are fixed-size integer slices of length 26, and the palindrome is constructed using string concatenation and reverse traversal of the left half.

Since all lengths are at most 300, there are no overflow concerns.

Worked Examples

Example 1

Input

s = "baba"
target = "abba"

Character counts:

Character	Count
a	2
b	2

Half counts:

Character	Half Count
a	1
b	1

Left-half length = 2.

Position 0

Try 'a'.

Maximum completion:

left = "ab"
palindrome = "abba"

"abba" > "abba" ?

No.

Try 'b'.

Maximum completion:

left = "ba"
palindrome = "baab"

"baab" > "abba"

Yes.

Choose 'b'.

Position 1

Only 'a' remains.

Choose 'a'.

Final palindrome:

baab

Output:

"baab"

Example 2

Input

s = "baba"
target = "bbaa"

Possible palindromes:

abba
baab

Both are less than "bbaa".

The greedy construction eventually finds that no feasible choice remains.

Output:

""

Example 3

Input

s = "abc"
target = "abb"

Counts:

Character	Count
a	1
b	1
c	1

Odd frequencies = 3.

A palindrome requires at most one odd frequency.

Output:

""

Example 4

Input

s = "aac"
target = "abb"

Counts:

Character	Count
a	2
c	1

Middle character:

c

Half counts:

a -> 1

Left half:

a

Palindrome:

aca

Comparison:

aca > abb

Output:

"aca"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(26 · n²) = O(n²)	Each position tries up to 26 characters and performs an O(n) feasibility check
Space	O(n)	Stores the palindrome prefix and temporary constructions

The left half contains at most n / 2 positions. For each position we may test up to 26 characters. Each feasibility test constructs and compares a palindrome of length n, giving O(26 · n²). Since 26 is constant, this simplifies to O(n²).

Test Cases

sol = Solution()

assert sol.lexPalindromicPermutation("baba", "abba") == "baab"  # example 1
assert sol.lexPalindromicPermutation("baba", "bbaa") == ""      # example 2
assert sol.lexPalindromicPermutation("abc", "abb") == ""        # no palindrome exists
assert sol.lexPalindromicPermutation("aac", "abb") == "aca"     # example 4

assert sol.lexPalindromicPermutation("a", "a") == ""            # single char equal
assert sol.lexPalindromicPermutation("a", "") == ""             # not valid input length, omitted in LC

assert sol.lexPalindromicPermutation("aaa", "aaa") == ""        # only palindrome equals target
assert sol.lexPalindromicPermutation("aaa", "aab") == ""        # only palindrome smaller

assert sol.lexPalindromicPermutation("aaa", "aaa") == ""        # no strictly larger palindrome
assert sol.lexPalindromicPermutation("aaaa", "aaaa") == ""      # unique palindrome

assert sol.lexPalindromicPermutation("aabb", "aaaa") == "abba"  # smallest valid palindrome
assert sol.lexPalindromicPermutation("aabbcc", "abccba") == "acbbca"  # later difference

assert sol.lexPalindromicPermutation("racecar", "aaaaaaa") == "acrerca"  # odd length case

Test Summary

Test	Why
("baba", "abba")	Basic successful case
("baba", "bbaa")	No palindrome exceeds target
("abc", "abb")	Palindrome impossible
("aac", "abb")	Unique palindrome succeeds
("a", "a")	Smallest valid size
("aaa", "aaa")	Unique palindrome equals target
("aaa", "aab")	Unique palindrome smaller than target
("aaaa", "aaaa")	Even-length unique palindrome
("aabb", "aaaa")	Multiple palindromic permutations
("aabbcc", "abccba")	Difference appears later
("racecar", "aaaaaaa")	Odd-length palindrome construction

Edge Cases

Multiple Odd Frequencies

A palindrome can contain at most one character with an odd count. If two or more characters have odd frequencies, constructing a palindrome is impossible.

For example:

s = "abc"

All three characters occur once. No palindrome can be formed, so the algorithm immediately returns "".

Only One Palindrome Exists

Sometimes the character frequencies uniquely determine the palindrome.

Example:

s = "aaaa"

The only palindrome is "aaaa".

If that palindrome is not strictly greater than target, there is no answer. The algorithm naturally handles this because every feasibility check eventually fails.

The First Difference Occurs Very Late

A common source of bugs is assuming the answer must differ from target near the beginning.

Example:

target = "abccba"

The correct answer might share a very long prefix and only become larger near the center. The greedy feasibility test correctly detects whether a future increase remains possible, allowing the algorithm to preserve the longest possible matching prefix before making the smallest necessary increase.