LeetCode #3734 — HARD

Lexicographically Smallest Palindromic Permutation Greater Than Target

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

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.

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Two Pointers

Example 1

"baba"
"abba"

Example 2

"baba"
"bbaa"

Example 3

"abc"
"abb"

Step 02

Core Insight

What unlocks the optimal approach

A palindromic permutation exists only if at most one character has an odd count (for odd-length strings) or all counts are even (for even-length strings).
Focus on constructing the first half of the palindrome. The second half is determined by mirroring.
To be lexicographically greater than target, the first half must be greater than or equal to target's first half, with careful handling of the middle character for odd-length strings.
Use a backtracking approach or greedy selection for each position in the first half, trying the smallest available character that can still produce a valid palindrome.
After building the first half, mirror it (and add the middle character if needed) to form the full palindrome and verify it is strictly greater than target.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3734: Lexicographically Smallest Palindromic Permutation Greater Than Target
// Auto-generated Java example from go.
class Solution {
    public void exampleSolution() {
    }
}
// Reference (go):
// // Accepted solution for LeetCode #3734: Lexicographically Smallest Palindromic Permutation Greater Than Target
// package main
// 
// import (
// 	"slices"
// 	"strings"
// )
// 
// // https://space.bilibili.com/206214
// func lexPalindromicPermutation1(s, target string) string {
// 	left := make([]int, 26)
// 	for _, b := range s {
// 		left[b-'a']++
// 	}
// 	valid := func() bool {
// 		for _, c := range left {
// 			if c < 0 {
// 				return false
// 			}
// 		}
// 		return true
// 	}
// 
// 	midCh := ""
// 	for i, c := range left {
// 		if c%2 == 0 {
// 			continue
// 		}
// 		// s 不能有超过一个字母出现奇数次
// 		if midCh != "" {
// 			return ""
// 		}
// 		// 记录填在正中间的字母
// 		midCh = string('a' + byte(i))
// 		left[i]--
// 	}
// 
// 	n := len(s)
// 	// 先假设答案左半与 t 的左半（不含正中间）相同
// 	for _, b := range target[:n/2] {
// 		left[b-'a'] -= 2
// 	}
// 
// 	if valid() {
// 		// 特殊情况：把 target 左半翻转到右半，能否比 target 大？
// 		leftS := target[:n/2]
// 		tmp := []byte(leftS)
// 		slices.Reverse(tmp)
// 		rightS := midCh + string(tmp)
// 		if rightS > target[n/2:] { // 由于左半是一样的，所以只需比右半
// 			return leftS + rightS
// 		}
// 	}
// 
// 	for i := n/2 - 1; i >= 0; i-- {
// 		b := target[i] - 'a'
// 		left[b] += 2  // 撤销消耗
// 		if !valid() { // [0,i-1] 无法做到全部一样
// 			continue
// 		}
// 
// 		// 把 target[i] 增大到 j
// 		for j := b + 1; j < 26; j++ {
// 			if left[j] == 0 {
// 				continue
// 			}
// 
// 			// 找到答案（下面的循环在整个算法中只会跑一次）
// 			left[j] -= 2
// 			ans := []byte(target[:i+1])
// 			ans[i] = 'a' + j
// 
// 			// 中间可以随便填
// 			for k, c := range left {
// 				ch := string('a' + byte(k))
// 				ans = append(ans, strings.Repeat(ch, c/2)...)
// 			}
// 
// 			// 镜像翻转
// 			rightS := slices.Clone(ans)
// 			slices.Reverse(rightS)
// 			ans = append(ans, midCh...)
// 			ans = append(ans, rightS...)
// 
// 			return string(ans)
// 		}
// 		// 增大失败，继续枚举
// 	}
// 	return ""
// }
// 
// func lexPalindromicPermutation(s, target string) string {
// 	left := make([]int, 26)
// 	for _, b := range s {
// 		left[b-'a']++
// 	}
// 
// 	midCh := ""
// 	for i, c := range left {
// 		if c%2 == 0 {
// 			continue
// 		}
// 		// s 不能有超过一个字母出现奇数次
// 		if midCh != "" {
// 			return ""
// 		}
// 		// 记录填在正中间的字母
// 		midCh = string('a' + byte(i))
// 		left[i]--
// 	}
// 
// 	n := len(s)
// 	// 先假设答案左半与 t 的左半（不含正中间）相同
// 	for _, b := range target[:n/2] {
// 		left[b-'a'] -= 2
// 	}
// 
// 	neg, leftMax := 0, byte(0)
// 	for i, cnt := range left {
// 		if cnt < 0 {
// 			neg++ // 统计 left 中的负数个数
// 		} else if cnt > 0 {
// 			leftMax = max(leftMax, byte(i)) // 剩余可用字母的最大值
// 		}
// 	}
// 
// 	if neg == 0 {
// 		// 特殊情况：把 target 左半翻转到右半，能否比 target 大？
// 		leftS := target[:n/2]
// 		tmp := []byte(leftS)
// 		slices.Reverse(tmp)
// 		rightS := midCh + string(tmp)
// 		if rightS > target[n/2:] { // 由于左半是一样的，所以只需比右半
// 			return leftS + rightS
// 		}
// 	}
// 
// 	for i := n/2 - 1; i >= 0; i-- {
// 		b := target[i] - 'a'
// 		left[b] += 2 // 撤销消耗
// 
// 		if left[b] == 0 {
// 			neg--
// 		} else if left[b] == 2 {
// 			leftMax = max(leftMax, b)
// 		}
// 
// 		// left 有负数 or 没有大于 target[i] 的字母
// 		if neg > 0 || leftMax <= b {
// 			continue
// 		}
// 
// 		// 找到答案（下面的循环在整个算法中只会跑一次）
// 		j := b + 1
// 		for left[j] == 0 {
// 			j++
// 		}
// 
// 		// 把 target[i] 和 target[n-1-i] 增大到 j
// 		left[j] -= 2
// 		ans := []byte(target[:i+1])
// 		ans[i] = 'a' + j
// 
// 		// 中间可以随便填
// 		for k, c := range left {
// 			ch := string('a' + byte(k))
// 			ans = append(ans, strings.Repeat(ch, c/2)...)
// 		}
// 
// 		// 镜像翻转
// 		rightS := slices.Clone(ans)
// 		slices.Reverse(rightS)
// 		ans = append(ans, midCh...)
// 		ans = append(ans, rightS...)
// 
// 		return string(ans)
// 	}
// 	return ""
// }

// Accepted solution for LeetCode #3734: Lexicographically Smallest Palindromic Permutation Greater Than Target
package main

import (
	"slices"
	"strings"
)

// https://space.bilibili.com/206214
func lexPalindromicPermutation1(s, target string) string {
	left := make([]int, 26)
	for _, b := range s {
		left[b-'a']++
	}
	valid := func() bool {
		for _, c := range left {
			if c < 0 {
				return false
			}
		}
		return true
	}

	midCh := ""
	for i, c := range left {
		if c%2 == 0 {
			continue
		}
		// s 不能有超过一个字母出现奇数次
		if midCh != "" {
			return ""
		}
		// 记录填在正中间的字母
		midCh = string('a' + byte(i))
		left[i]--
	}

	n := len(s)
	// 先假设答案左半与 t 的左半（不含正中间）相同
	for _, b := range target[:n/2] {
		left[b-'a'] -= 2
	}

	if valid() {
		// 特殊情况：把 target 左半翻转到右半，能否比 target 大？
		leftS := target[:n/2]
		tmp := []byte(leftS)
		slices.Reverse(tmp)
		rightS := midCh + string(tmp)
		if rightS > target[n/2:] { // 由于左半是一样的，所以只需比右半
			return leftS + rightS
		}
	}

	for i := n/2 - 1; i >= 0; i-- {
		b := target[i] - 'a'
		left[b] += 2  // 撤销消耗
		if !valid() { // [0,i-1] 无法做到全部一样
			continue
		}

		// 把 target[i] 增大到 j
		for j := b + 1; j < 26; j++ {
			if left[j] == 0 {
				continue
			}

			// 找到答案（下面的循环在整个算法中只会跑一次）
			left[j] -= 2
			ans := []byte(target[:i+1])
			ans[i] = 'a' + j

			// 中间可以随便填
			for k, c := range left {
				ch := string('a' + byte(k))
				ans = append(ans, strings.Repeat(ch, c/2)...)
			}

			// 镜像翻转
			rightS := slices.Clone(ans)
			slices.Reverse(rightS)
			ans = append(ans, midCh...)
			ans = append(ans, rightS...)

			return string(ans)
		}
		// 增大失败，继续枚举
	}
	return ""
}

func lexPalindromicPermutation(s, target string) string {
	left := make([]int, 26)
	for _, b := range s {
		left[b-'a']++
	}

	midCh := ""
	for i, c := range left {
		if c%2 == 0 {
			continue
		}
		// s 不能有超过一个字母出现奇数次
		if midCh != "" {
			return ""
		}
		// 记录填在正中间的字母
		midCh = string('a' + byte(i))
		left[i]--
	}

	n := len(s)
	// 先假设答案左半与 t 的左半（不含正中间）相同
	for _, b := range target[:n/2] {
		left[b-'a'] -= 2
	}

	neg, leftMax := 0, byte(0)
	for i, cnt := range left {
		if cnt < 0 {
			neg++ // 统计 left 中的负数个数
		} else if cnt > 0 {
			leftMax = max(leftMax, byte(i)) // 剩余可用字母的最大值
		}
	}

	if neg == 0 {
		// 特殊情况：把 target 左半翻转到右半，能否比 target 大？
		leftS := target[:n/2]
		tmp := []byte(leftS)
		slices.Reverse(tmp)
		rightS := midCh + string(tmp)
		if rightS > target[n/2:] { // 由于左半是一样的，所以只需比右半
			return leftS + rightS
		}
	}

	for i := n/2 - 1; i >= 0; i-- {
		b := target[i] - 'a'
		left[b] += 2 // 撤销消耗

		if left[b] == 0 {
			neg--
		} else if left[b] == 2 {
			leftMax = max(leftMax, b)
		}

		// left 有负数 or 没有大于 target[i] 的字母
		if neg > 0 || leftMax <= b {
			continue
		}

		// 找到答案（下面的循环在整个算法中只会跑一次）
		j := b + 1
		for left[j] == 0 {
			j++
		}

		// 把 target[i] 和 target[n-1-i] 增大到 j
		left[j] -= 2
		ans := []byte(target[:i+1])
		ans[i] = 'a' + j

		// 中间可以随便填
		for k, c := range left {
			ch := string('a' + byte(k))
			ans = append(ans, strings.Repeat(ch, c/2)...)
		}

		// 镜像翻转
		rightS := slices.Clone(ans)
		slices.Reverse(rightS)
		ans = append(ans, midCh...)
		ans = append(ans, rightS...)

		return string(ans)
	}
	return ""
}

# Accepted solution for LeetCode #3734: Lexicographically Smallest Palindromic Permutation Greater Than Target
#
# @lc app=leetcode id=3734 lang=python3
#
# [3734] Lexicographically Smallest Palindromic Permutation Greater Than Target
#
# @lc code=start
class Solution:
    def lexPalindromicPermutation(self, s: str, target: str) -> str:
        from collections import Counter

        n = len(s)
        count = Counter(s)
        
        # Check if palindrome is possible
        odd_char = ''
        odd_counts = 0
        for char in count:
            if count[char] % 2 != 0:
                odd_counts += 1
                odd_char = char
        
        if odd_counts > 1:
            return ""
        
        # Prepare counts for the first half
        half_count = Counter()
        for char, c in count.items():
            half_count[char] = c // 2
            
        m = n // 2
        
        # We want to find the longest prefix of target[0...m-1] we can match,
        # then deviate with a larger character.
        # Or, if n is odd, match target[0...m-1] and find a valid middle char.
        
        # To do this correctly, we iterate backwards from the deviation point.
        # The deviation point i is where our result[i] > target[i].
        # We want the largest possible i (longest matching prefix).
        # Range of i is m down to 0 (if n is odd, we check middle at m).
        
        # Precompute availability of prefixes
        # valid_prefix_len is the length of the longest prefix of target's half we can form.
        temp_half = half_count.copy()
        valid_prefix_len = 0
        for i in range(m):
            char = target[i]
            if temp_half[char] > 0:
                temp_half[char] -= 1
                valid_prefix_len += 1
            else:
                break
        
        # Helper to construct result
        def build_result(prefix_len, deviation_char, current_half_counts):
            # Prefix is target[:prefix_len]
            # Deviation is deviation_char at index prefix_len
            # Rest is filled greedily
            
            res_half = list(target[:prefix_len])
            res_half.append(deviation_char)
            
            # Decrement deviation char count
            current_half_counts[deviation_char] -= 1
            
            # Fill remaining m - 1 - prefix_len characters
            sorted_chars = sorted(current_half_counts.keys())
            for char in sorted_chars:
                count = current_half_counts[char]
                res_half.extend([char] * count)
            
            first_half_str = "".join(res_half)
            
            mid_str = odd_char if n % 2 != 0 else ""
            
            return first_half_str + mid_str + first_half_str[::-1]

        # Case 1: n is odd. Try to match full half, then check middle.
        if n % 2 != 0:
            # Can we match target[0...m-1]?
            if valid_prefix_len == m:
                # We have the half. Now we need to check the middle character.
                # The current palindrome would be target[:m] + odd_char + reversed(target[:m])
                # Is this > target? 
                # Since the first half matches target, we compare the rest.
                # constructed: ... + odd_char + reversed(first_half)
                # target:      ... + target[m] + target[m+1...]
                
                # Actually, simpler logic: The first half is fixed to target[:m].
                # The middle char is fixed to odd_char.
                # The second half is fixed to reversed(target[:m]).
                # So there is only ONE permutation that matches the first half target[:m].
                # We just check if it is > target.
                
                cand = target[:m] + odd_char + target[:m][::-1]
                if cand > target:
                    return cand
        else:
             # If n is even, and we match fully, the palindrome is target[:m] + target[:m][::-1]
             if valid_prefix_len == m:
                 cand = target[:m] + target[:m][::-1]
                 if cand > target:
                     return cand

        # Case 2: Deviate at index i (from m-1 down to 0)
        # We need to maintain the counts corresponding to target[:i]
        # We can re-calculate counts or backtrack. Since m is small (<= 150), re-calc is fine or manage state.
        # Let's manage state. We start with counts for the full valid prefix and backtrack.
        
        # Current counts used for the longest valid prefix
        curr_counts = half_count.copy()
        for i in range(valid_prefix_len):
            curr_counts[target[i]] -= 1
            
        # Iterate i from valid_prefix_len down to 0
        # At index i, we try to put char c > target[i]
        # The prefix target[:i] is valid by definition of loop direction.
        # After checking i, we "give back" target[i-1] to counts for the next iteration (i-1).
        
        # Note: valid_prefix_len could be m. We check deviation at m-1, m-2...
        # If valid_prefix_len < m, we can't deviate at valid_prefix_len (because we can't even place target[valid_prefix_len]),
        # but we can try to place something > target[valid_prefix_len] IF we have it.
        # Actually, if we can't match target[i], we MUST deviate at i or earlier.
        # So we start checking at i = valid_prefix_len.
        
        # If valid_prefix_len == m, we already checked the "match all" case above.
        # So we start strictly looking for deviations.
        
        start_i = valid_prefix_len
        # If we matched everything (m), we start deviating at m-1.
        if start_i == m:
            start_i = m - 1
            # We need to restore the count for the char we are about to remove (target[m-1])
            # implicitly handled by the loop structure logic below if we align it right.
            # Let's align: curr_counts matches target[:valid_prefix_len].
            # If we want to deviate at i, we need counts for target[:i].
        
        # Let's adjust curr_counts to represent target[:start_i]
        # If valid_prefix_len == m, curr_counts has consumed all m chars.
        # We want to start loop at m-1. We need to put back target[m-1...start_i-1]?? No.
        # Let's just fix the loop.
        
        # Correct state management:
        # curr_counts currently reflects consumption of target[:valid_prefix_len].
        
        for i in range(start_i, -1, -1):
            # At this index i, we want to place a char > target[i].
            # First, if i < valid_prefix_len, it means we are backtracking, so we must return target[i] to counts.
            if i < valid_prefix_len:
                curr_counts[target[i]] += 1
            
            # Now curr_counts reflects target[:i].
            # Find smallest char in curr_counts > target[i]
            found_char = None
            for char in sorted(curr_counts.keys()):
                if curr_counts[char] > 0 and char > target[i]:
                    found_char = char
                    break
            
            if found_char:
                return build_result(i, found_char, curr_counts)
        
        return ""
# @lc code=end

// Accepted solution for LeetCode #3734: Lexicographically Smallest Palindromic Permutation Greater Than Target
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (go):
// // Accepted solution for LeetCode #3734: Lexicographically Smallest Palindromic Permutation Greater Than Target
// package main
// 
// import (
// 	"slices"
// 	"strings"
// )
// 
// // https://space.bilibili.com/206214
// func lexPalindromicPermutation1(s, target string) string {
// 	left := make([]int, 26)
// 	for _, b := range s {
// 		left[b-'a']++
// 	}
// 	valid := func() bool {
// 		for _, c := range left {
// 			if c < 0 {
// 				return false
// 			}
// 		}
// 		return true
// 	}
// 
// 	midCh := ""
// 	for i, c := range left {
// 		if c%2 == 0 {
// 			continue
// 		}
// 		// s 不能有超过一个字母出现奇数次
// 		if midCh != "" {
// 			return ""
// 		}
// 		// 记录填在正中间的字母
// 		midCh = string('a' + byte(i))
// 		left[i]--
// 	}
// 
// 	n := len(s)
// 	// 先假设答案左半与 t 的左半（不含正中间）相同
// 	for _, b := range target[:n/2] {
// 		left[b-'a'] -= 2
// 	}
// 
// 	if valid() {
// 		// 特殊情况：把 target 左半翻转到右半，能否比 target 大？
// 		leftS := target[:n/2]
// 		tmp := []byte(leftS)
// 		slices.Reverse(tmp)
// 		rightS := midCh + string(tmp)
// 		if rightS > target[n/2:] { // 由于左半是一样的，所以只需比右半
// 			return leftS + rightS
// 		}
// 	}
// 
// 	for i := n/2 - 1; i >= 0; i-- {
// 		b := target[i] - 'a'
// 		left[b] += 2  // 撤销消耗
// 		if !valid() { // [0,i-1] 无法做到全部一样
// 			continue
// 		}
// 
// 		// 把 target[i] 增大到 j
// 		for j := b + 1; j < 26; j++ {
// 			if left[j] == 0 {
// 				continue
// 			}
// 
// 			// 找到答案（下面的循环在整个算法中只会跑一次）
// 			left[j] -= 2
// 			ans := []byte(target[:i+1])
// 			ans[i] = 'a' + j
// 
// 			// 中间可以随便填
// 			for k, c := range left {
// 				ch := string('a' + byte(k))
// 				ans = append(ans, strings.Repeat(ch, c/2)...)
// 			}
// 
// 			// 镜像翻转
// 			rightS := slices.Clone(ans)
// 			slices.Reverse(rightS)
// 			ans = append(ans, midCh...)
// 			ans = append(ans, rightS...)
// 
// 			return string(ans)
// 		}
// 		// 增大失败，继续枚举
// 	}
// 	return ""
// }
// 
// func lexPalindromicPermutation(s, target string) string {
// 	left := make([]int, 26)
// 	for _, b := range s {
// 		left[b-'a']++
// 	}
// 
// 	midCh := ""
// 	for i, c := range left {
// 		if c%2 == 0 {
// 			continue
// 		}
// 		// s 不能有超过一个字母出现奇数次
// 		if midCh != "" {
// 			return ""
// 		}
// 		// 记录填在正中间的字母
// 		midCh = string('a' + byte(i))
// 		left[i]--
// 	}
// 
// 	n := len(s)
// 	// 先假设答案左半与 t 的左半（不含正中间）相同
// 	for _, b := range target[:n/2] {
// 		left[b-'a'] -= 2
// 	}
// 
// 	neg, leftMax := 0, byte(0)
// 	for i, cnt := range left {
// 		if cnt < 0 {
// 			neg++ // 统计 left 中的负数个数
// 		} else if cnt > 0 {
// 			leftMax = max(leftMax, byte(i)) // 剩余可用字母的最大值
// 		}
// 	}
// 
// 	if neg == 0 {
// 		// 特殊情况：把 target 左半翻转到右半，能否比 target 大？
// 		leftS := target[:n/2]
// 		tmp := []byte(leftS)
// 		slices.Reverse(tmp)
// 		rightS := midCh + string(tmp)
// 		if rightS > target[n/2:] { // 由于左半是一样的，所以只需比右半
// 			return leftS + rightS
// 		}
// 	}
// 
// 	for i := n/2 - 1; i >= 0; i-- {
// 		b := target[i] - 'a'
// 		left[b] += 2 // 撤销消耗
// 
// 		if left[b] == 0 {
// 			neg--
// 		} else if left[b] == 2 {
// 			leftMax = max(leftMax, b)
// 		}
// 
// 		// left 有负数 or 没有大于 target[i] 的字母
// 		if neg > 0 || leftMax <= b {
// 			continue
// 		}
// 
// 		// 找到答案（下面的循环在整个算法中只会跑一次）
// 		j := b + 1
// 		for left[j] == 0 {
// 			j++
// 		}
// 
// 		// 把 target[i] 和 target[n-1-i] 增大到 j
// 		left[j] -= 2
// 		ans := []byte(target[:i+1])
// 		ans[i] = 'a' + j
// 
// 		// 中间可以随便填
// 		for k, c := range left {
// 			ch := string('a' + byte(k))
// 			ans = append(ans, strings.Repeat(ch, c/2)...)
// 		}
// 
// 		// 镜像翻转
// 		rightS := slices.Clone(ans)
// 		slices.Reverse(rightS)
// 		ans = append(ans, midCh...)
// 		ans = append(ans, rightS...)
// 
// 		return string(ans)
// 	}
// 	return ""
// }

// Accepted solution for LeetCode #3734: Lexicographically Smallest Palindromic Permutation Greater Than Target
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3734: Lexicographically Smallest Palindromic Permutation Greater Than Target
// package main
// 
// import (
// 	"slices"
// 	"strings"
// )
// 
// // https://space.bilibili.com/206214
// func lexPalindromicPermutation1(s, target string) string {
// 	left := make([]int, 26)
// 	for _, b := range s {
// 		left[b-'a']++
// 	}
// 	valid := func() bool {
// 		for _, c := range left {
// 			if c < 0 {
// 				return false
// 			}
// 		}
// 		return true
// 	}
// 
// 	midCh := ""
// 	for i, c := range left {
// 		if c%2 == 0 {
// 			continue
// 		}
// 		// s 不能有超过一个字母出现奇数次
// 		if midCh != "" {
// 			return ""
// 		}
// 		// 记录填在正中间的字母
// 		midCh = string('a' + byte(i))
// 		left[i]--
// 	}
// 
// 	n := len(s)
// 	// 先假设答案左半与 t 的左半（不含正中间）相同
// 	for _, b := range target[:n/2] {
// 		left[b-'a'] -= 2
// 	}
// 
// 	if valid() {
// 		// 特殊情况：把 target 左半翻转到右半，能否比 target 大？
// 		leftS := target[:n/2]
// 		tmp := []byte(leftS)
// 		slices.Reverse(tmp)
// 		rightS := midCh + string(tmp)
// 		if rightS > target[n/2:] { // 由于左半是一样的，所以只需比右半
// 			return leftS + rightS
// 		}
// 	}
// 
// 	for i := n/2 - 1; i >= 0; i-- {
// 		b := target[i] - 'a'
// 		left[b] += 2  // 撤销消耗
// 		if !valid() { // [0,i-1] 无法做到全部一样
// 			continue
// 		}
// 
// 		// 把 target[i] 增大到 j
// 		for j := b + 1; j < 26; j++ {
// 			if left[j] == 0 {
// 				continue
// 			}
// 
// 			// 找到答案（下面的循环在整个算法中只会跑一次）
// 			left[j] -= 2
// 			ans := []byte(target[:i+1])
// 			ans[i] = 'a' + j
// 
// 			// 中间可以随便填
// 			for k, c := range left {
// 				ch := string('a' + byte(k))
// 				ans = append(ans, strings.Repeat(ch, c/2)...)
// 			}
// 
// 			// 镜像翻转
// 			rightS := slices.Clone(ans)
// 			slices.Reverse(rightS)
// 			ans = append(ans, midCh...)
// 			ans = append(ans, rightS...)
// 
// 			return string(ans)
// 		}
// 		// 增大失败，继续枚举
// 	}
// 	return ""
// }
// 
// func lexPalindromicPermutation(s, target string) string {
// 	left := make([]int, 26)
// 	for _, b := range s {
// 		left[b-'a']++
// 	}
// 
// 	midCh := ""
// 	for i, c := range left {
// 		if c%2 == 0 {
// 			continue
// 		}
// 		// s 不能有超过一个字母出现奇数次
// 		if midCh != "" {
// 			return ""
// 		}
// 		// 记录填在正中间的字母
// 		midCh = string('a' + byte(i))
// 		left[i]--
// 	}
// 
// 	n := len(s)
// 	// 先假设答案左半与 t 的左半（不含正中间）相同
// 	for _, b := range target[:n/2] {
// 		left[b-'a'] -= 2
// 	}
// 
// 	neg, leftMax := 0, byte(0)
// 	for i, cnt := range left {
// 		if cnt < 0 {
// 			neg++ // 统计 left 中的负数个数
// 		} else if cnt > 0 {
// 			leftMax = max(leftMax, byte(i)) // 剩余可用字母的最大值
// 		}
// 	}
// 
// 	if neg == 0 {
// 		// 特殊情况：把 target 左半翻转到右半，能否比 target 大？
// 		leftS := target[:n/2]
// 		tmp := []byte(leftS)
// 		slices.Reverse(tmp)
// 		rightS := midCh + string(tmp)
// 		if rightS > target[n/2:] { // 由于左半是一样的，所以只需比右半
// 			return leftS + rightS
// 		}
// 	}
// 
// 	for i := n/2 - 1; i >= 0; i-- {
// 		b := target[i] - 'a'
// 		left[b] += 2 // 撤销消耗
// 
// 		if left[b] == 0 {
// 			neg--
// 		} else if left[b] == 2 {
// 			leftMax = max(leftMax, b)
// 		}
// 
// 		// left 有负数 or 没有大于 target[i] 的字母
// 		if neg > 0 || leftMax <= b {
// 			continue
// 		}
// 
// 		// 找到答案（下面的循环在整个算法中只会跑一次）
// 		j := b + 1
// 		for left[j] == 0 {
// 			j++
// 		}
// 
// 		// 把 target[i] 和 target[n-1-i] 增大到 j
// 		left[j] -= 2
// 		ans := []byte(target[:i+1])
// 		ans[i] = 'a' + j
// 
// 		// 中间可以随便填
// 		for k, c := range left {
// 			ch := string('a' + byte(k))
// 			ans = append(ans, strings.Repeat(ch, c/2)...)
// 		}
// 
// 		// 镜像翻转
// 		rightS := slices.Clone(ans)
// 		slices.Reverse(rightS)
// 		ans = append(ans, midCh...)
// 		ans = append(ans, rightS...)
// 
// 		return string(ans)
// 	}
// 	return ""
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(1)

Approach Breakdown

BRUTE FORCE

O(n²) time

O(1) space

Two nested loops check every pair of elements. The outer loop picks one element, the inner loop scans the rest. For n elements that is n × (n−1)/2 comparisons = O(n²). No extra memory — just two loop variables.

TWO POINTERS

O(n) time

O(1) space

Each pointer traverses the array at most once. With two pointers moving inward (or both moving right), the total number of steps is bounded by n. Each comparison is O(1), giving O(n) overall. No auxiliary data structures are needed — just two index variables.

Shortcut: Two converging pointers on sorted data → O(n) time, O(1) space.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Moving both pointers on every comparison

Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.

Usually fails on: A valid pair can be skipped when only one side should move.

Fix: Move exactly one pointer per decision branch based on invariant.