Welcome to Subscribe On Youtube

3517. Smallest Palindromic Rearrangement I

Description

You are given a palindromic string s.

Return the lexicographically smallest palindromic permutation of s.

 

Example 1:

Input: s = "z"

Output: "z"

Explanation:

A string of only one character is already the lexicographically smallest palindrome.

Example 2:

Input: s = "babab"

Output: "abbba"

Explanation:

Rearranging "babab" → "abbba" gives the smallest lexicographic palindrome.

Example 3:

Input: s = "daccad"

Output: "acddca"

Explanation:

Rearranging "daccad" → "acddca" gives the smallest lexicographic palindrome.

 

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters.
• s is guaranteed to be palindromic.

Solutions

Solution 1

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public String smallestPalindrome(String s) {
          int[] cnt = new int[26];
          for (char c : s.toCharArray()) {
              cnt[c - 'a']++;
          }
  
          StringBuilder t = new StringBuilder();
          String ch = "";
  
          for (char c = 'a'; c <= 'z'; c++) {
              int idx = c - 'a';
              int v = cnt[idx] / 2;
              if (v > 0) {
                  t.append(String.valueOf(c).repeat(v));
              }
              cnt[idx] -= v * 2;
              if (cnt[idx] == 1) {
                  ch = String.valueOf(c);
              }
          }
  
          String ans = t.toString();
          ans = ans + ch + new StringBuilder(ans).reverse();
          return ans;
      }
  }
  
  

• class Solution {
  public:
      string smallestPalindrome(string s) {
          vector<int> cnt(26);
          for (char c : s) {
              cnt[c - 'a']++;
          }
          string t = "";
          string ch = "";
          for (char c = 'a'; c <= 'z'; ++c) {
              int v = cnt[c - 'a'] / 2;
              if (v > 0) {
                  t.append(v, c);
              }
              cnt[c - 'a'] -= v * 2;
              if (cnt[c - 'a'] == 1) {
                  ch = string(1, c);
              }
          }
          string ans = t;
          ans += ch;
          string rev = t;
          reverse(rev.begin(), rev.end());
          ans += rev;
          return ans;
      }
  };
  
  

• class Solution:
      def smallestPalindrome(self, s: str) -> str:
          cnt = Counter(s)
          t = []
          ch = ""
          for c in ascii_lowercase:
              v = cnt[c] // 2
              t.append(c * v)
              cnt[c] -= v * 2
              if cnt[c] == 1:
                  ch = c
          ans = "".join(t)
          ans = ans + ch + ans[::-1]
          return ans
  
  

• func smallestPalindrome(s string) string {
  	cnt := make([]int, 26)
  	for i := 0; i < len(s); i++ {
  		cnt[s[i]-'a']++
  	}
  
  	t := make([]byte, 0, len(s)/2)
  	var ch byte
  	for c := byte('a'); c <= 'z'; c++ {
  		v := cnt[c-'a'] / 2
  		for i := 0; i < v; i++ {
  			t = append(t, c)
  		}
  		cnt[c-'a'] -= v * 2
  		if cnt[c-'a'] == 1 {
  			ch = c
  		}
  	}
  
  	totalLen := len(t) * 2
  	if ch != 0 {
  		totalLen++
  	}
  	var sb strings.Builder
  	sb.Grow(totalLen)
  
  	sb.Write(t)
  	if ch != 0 {
  		sb.WriteByte(ch)
  	}
  	for i := len(t) - 1; i >= 0; i-- {
  		sb.WriteByte(t[i])
  	}
  	return sb.String()
  }
  
  

• function smallestPalindrome(s: string): string {
      const ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz';
      const cnt = new Array<number>(26).fill(0);
      for (const chKey of s) {
          cnt[chKey.charCodeAt(0) - 97]++;
      }
  
      const t: string[] = [];
      let ch = '';
      for (let i = 0; i < 26; i++) {
          const c = ascii_lowercase[i];
          const v = Math.floor(cnt[i] / 2);
          t.push(c.repeat(v));
          cnt[i] -= v * 2;
          if (cnt[i] === 1) {
              ch = c;
          }
      }
  
      let ans = t.join('');
      ans = ans + ch + ans.split('').reverse().join('');
      return ans;
  }
  
  

All Problems

All Solutions