Skip to content

3517. Smallest Palindromic Rearrangement I 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  string smallestPalindrome(string s) {
    const int n = s.length();
    const string sortedHalf = getSortedHalf(s);
    return sortedHalf + (n % 2 ? string(1, s[n / 2]) : "") +
           reversed(sortedHalf);
  }

 private:
  string getSortedHalf(const string& s) {
    string half = s.substr(0, s.length() / 2);
    ranges::sort(half);
    return half;
  }

  string reversed(const string& s) {
    return {s.rbegin(), s.rend()};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public String smallestPalindrome(String s) {
    final int n = s.length();
    final String sortedHalf = getSortedHalf(s);
    return sortedHalf + (n % 2 == 1 ? String.valueOf(s.charAt(n / 2)) : "") + reversed(sortedHalf);
  }

  private String getSortedHalf(final String s) {
    final String half = s.substring(0, s.length() / 2);
    char[] chars = half.toCharArray();
    Arrays.sort(chars);
    return new String(chars);
  }

  private String reversed(final String s) {
    return new StringBuilder(s).reverse().toString();
  }
}

1
2
3
4
5
6
7
class Solution:
  def smallestPalindrome(self, s: str) -> str:
    n = len(s)
    sortedHalf = sorted(s[:n // 2])
    return ''.join(sortedHalf +
                   ([s[n // 2]] if n % 2 else []) +
                   sortedHalf[::-1])