Palindrome Permutation Ii - Leetcode Solution

Problem Description: Given a string s, return all the palindrome permutations of s. You may return the answer in any order.

Examples: Input: s = "aabb" Output: ["abba","baab"]

Input: s = "abc" Output: []

Solution: We can use a backtracking approach to solve this problem. Firstly, we need to find all possible permutations of the given string. Then, we will check whether the permutation is a palindrome or not. If it's a palindrome, then we will add it to our result.

To find all permutations, we will use a recursive function. The function will take the current string, the result list, and the index of the element we need to swap. Initially, the index will be 0. We will swap the element at the current index with all the elements, including itself. Then, we will call the same function with the updated string, the result list, and the next index.

After finding all the permutations, we will check whether each permutation is a palindrome or not. To check whether it's a palindrome or not, we will iterate through the string from both ends. If all characters are matching, then it's a palindrome.

Here's the implementation of the solution in Python:

def palindromePermutation(s): res = [] permute(list(s), 0, res) return res

def permute(arr, l, res): if l == len(arr): res.append(''.join(arr))

for i in range(l, len(arr)):
    if i != l and arr[i] == arr[l]:
        continue
    arr[l], arr[i] = arr[i], arr[l]
    permute(arr, l+1, res)
    arr[l], arr[i] = arr[i], arr[l]

def isPalindrome(s): return s == s[::-1]

ans = [] s = "aabb" perms = set(palindromePermutation(s)) for perm in perms: if isPalindrome(perm): ans.append(perm)

print(ans)

Output: ['abba', 'baab']

Time Complexity: The time complexity of the solution is O(n!*n), where n is the length of the given string. This is because we are finding all permutations of the given string, which takes n! time, and for each permutation, we are checking whether it's a palindrome or not, which takes n time. Therefore, the overall time complexity will be O(n!*n).

Space Complexity: The space complexity of the solution is O(n!*n), where n is the length of the given string. This is because we need to store all possible permutations of the string, which takes n! space, and each permutation can have a maximum of n characters, so the overall space complexity will be O(n!*n).

1