Skip to content

267. Palindrome Permutation II 👍

  • Time: $O(n^n)$
  • Space: $O(|\texttt{ans}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
 public:
  vector<string> generatePalindromes(string s) {
    int odd = 0;
    unordered_map<char, int> count;

    for (const char c : s)
      ++count[c];

    // Count odd ones.
    for (const auto& [_, value] : count)
      if (value & 1)
        ++odd;

    // Can't form any palindrome.
    if (odd > 1)
      return {};

    vector<string> ans;
    vector<char> candidates;
    string mid;

    // Get the mid and the candidates characters.
    for (const auto& [key, value] : count) {
      if (value & 1)
        mid += key;
      for (int i = 0; i < value / 2; ++i)
        candidates.push_back(key);
    }

    // Backtrack to generate the ans strings.
    dfs(candidates, mid, vector<bool>(candidates.size()), "", ans);
    return ans;
  }

 private:
  // Generates all the unique palindromes from the candidates.
  void dfs(const vector<char>& candidates, const string& mid,
           vector<bool>&& used, string&& path, vector<string>& ans) {
    if (path.length() == candidates.size()) {
      string secondHalf = path;
      reverse(secondHalf.begin(), secondHalf.end());
      ans.push_back(path + mid + secondHalf);
      return;
    }

    for (int i = 0; i < candidates.size(); ++i) {
      if (used[i])
        continue;
      if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1])
        continue;
      used[i] = true;
      path.push_back(candidates[i]);
      dfs(candidates, mid, move(used), move(path), ans);
      path.pop_back();
      used[i] = false;
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
  public List<String> generatePalindromes(String s) {
    int odd = 0;
    Map<Character, Integer> count = new HashMap<>();

    for (final char c : s.toCharArray())
      count.merge(c, 1, Integer::sum);

    // Count odd ones.
    for (Map.Entry<Character, Integer> entry : count.entrySet())
      if (entry.getValue() % 2 == 1)
        ++odd;

    // Can't form any palindrome.
    if (odd > 1)
      return new ArrayList<>();

    List<String> ans = new ArrayList<>();
    List<Character> candidates = new ArrayList<>();
    StringBuilder mid = new StringBuilder();

    // Get the mid and the candidates characters.
    for (Map.Entry<Character, Integer> entry : count.entrySet()) {
      final char key = entry.getKey();
      final int value = entry.getValue();
      if (value % 2 == 1)
        mid.append(key);
      for (int i = 0; i < value / 2; ++i)
        candidates.add(key);
    }

    // Backtrack to generate the ans strings.
    dfs(candidates, mid, new boolean[candidates.size()], new StringBuilder(), ans);
    return ans;
  }

  // Generates all the unique palindromes from the candidates.
  private void dfs(List<Character> candidates, StringBuilder mid, boolean[] used, StringBuilder sb,
                   List<String> ans) {
    if (sb.length() == candidates.size()) {
      ans.add(sb.toString() + mid + sb.reverse().toString());
      sb.reverse();
      return;
    }

    for (int i = 0; i < candidates.size(); ++i) {
      if (used[i])
        continue;
      if (i > 0 && candidates.get(i) == candidates.get(i - 1) && !used[i - 1])
        continue;
      used[i] = true;
      sb.append(candidates.get(i));
      dfs(candidates, mid, used, sb, ans);
      sb.deleteCharAt(sb.length() - 1);
      used[i] = false;
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
  def generatePalindromes(self, s: str) -> List[str]:
    count = collections.Counter(s)

    # Count odd ones.
    odd = sum(value & 1 for value in count.values())

    # Can't form any palindrome.
    if odd > 1:
      return []

    ans = []
    candidates = []
    mid = ''

    # Get the mid and the candidates characters.
    for key, value in count.items():
      if value & 1:
        mid += key
      for _ in range(value // 2):
        candidates.append(key)

    def dfs(used: List[bool], path: List[chr]) -> None:
      """Generates all the unique palindromes from the candidates."""
      if len(path) == len(candidates):
        ans.append(''.join(path) + mid + ''.join(reversed(path)))
        return

      for i, candidate in enumerate(candidates):
        if used[i]:
          continue
        if i > 0 and candidate == candidates[i - 1] and not used[i - 1]:
          continue
        used[i] = True
        path.append(candidate)
        dfs(used, path)
        path.pop()
        used[i] = False

    # Backtrack to generate the ans strings.
    dfs([False] * len(candidates), [])
    return ans