lexicographically-smallest-palindromic-permutation-greater-than-target

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

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

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

&nbsp;
Example 1:

<div class="example-block">
Input: s = &quot;baba&quot;, target = &quot;abba&quot;

Output: &quot;baab&quot;

Explanation:

<ul>
	<li>The palindromic permutations of <code>s</code> (in lexicographical order) are <code>&quot;abba&quot;</code> and <code>&quot;baab&quot;</code>.</li>
	<li>The lexicographically smallest permutation that is strictly greater than <code>target</code> is <code>&quot;baab&quot;</code>.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: s = &quot;baba&quot;, target = &quot;bbaa&quot;

Output: &quot;&quot;

Explanation:

<ul>
	<li>The palindromic permutations of <code>s</code> (in lexicographical order) are <code>&quot;abba&quot;</code> and <code>&quot;baab&quot;</code>.</li>
	<li>None of them is lexicographically strictly greater than <code>target</code>. Therefore, the answer is <code>&quot;&quot;</code>.</li>
</ul>
</div>

Example 3:

<div class="example-block">
Input: s = &quot;abc&quot;, target = &quot;abb&quot;

Output: &quot;&quot;

Explanation:

<code>s</code> has no palindromic permutations. Therefore, the answer is <code>&quot;&quot;</code>.
</div>

Example 4:

<div class="example-block">
Input: s = &quot;aac&quot;, target = &quot;abb&quot;

Output: &quot;aca&quot;

Explanation:

<ul>
	<li>The only palindromic permutation of <code>s</code> is <code>&quot;aca&quot;</code>.</li>
	<li><code>&quot;aca&quot;</code> is strictly greater than <code>target</code>. Therefore, the answer is <code>&quot;aca&quot;</code>.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n == s.length == target.length &lt;= 300</code></li>
	<li><code>s</code> and <code>target</code> consist of only lowercase English letters.</li>
</ul>