# Minimum insertions to form a palindrome with permutations allowed

Given a string of lowercase letters. Find minimum characters to be inserted in string so that it can become palindrome. We can change positions of characters in string.

Examples:

```Input : geeksforgeeks
Output : 2
geeksforgeeks can be changed as:
geeksroforskeeg
geeksorfroskeeg
and many more

Input : aabbc
Output : 0
aabbc can be changed as:
abcba
bacab
```

A palindromic string can have one odd character only when length of string is odd otherwise all characters occur even number of times. So, we have to find characters which occur odd times in a string.

The idea is to count occurrence of each character in a string. As palindromic string can have one character which occur odd times so number of insertion will be one less then count of characters which occur odd times. And if string is already palindrome, we do not need to add any character so result will be 0.

## C++

 `// CPP program to find minimum number ` `// of insertions to make a string ` `// palindrome ` `#include ` `using` `namespace` `std; ` ` `  `// Function will return number of ` `// characters to be added ` `int` `minInsertion(string str) ` `{ ` `    ``// To store string length ` `    ``int` `n = str.length(); ` ` `  `    ``// To store number of characters ` `    ``// occurring odd number of times ` `    ``int` `res = 0; ` ` `  `    ``// To store count of each ` `    ``// character ` `    ``int` `count = { 0 }; ` ` `  `    ``// To store occurrence of each ` `    ``// character ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``count[str[i] - ``'a'``]++; ` ` `  `    ``// To count characters with odd ` `    ``// occurrence ` `    ``for` `(``int` `i = 0; i < 26; i++) ` `        ``if` `(count[i] % 2 == 1) ` `            ``res++; ` ` `  `    ``// As one character can be odd return ` `    ``// res - 1 but if string is already ` `    ``// palindrome return 0 ` `    ``return` `(res == 0) ? 0 : res - 1; ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `    ``string str = ``"geeksforgeeks"``; ` `    ``cout << minInsertion(str); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to find minimum number ` `// of insertions to make a string ` `// palindrome ` `public` `class` `Palindrome { ` ` `  `    ``// Function will return number of ` `    ``// characters to be added ` `    ``static` `int` `minInsertion(String str) ` `    ``{ ` `        ``// To store string length ` `        ``int` `n = str.length(); ` ` `  `        ``// To store number of characters ` `        ``// occurring odd number of times ` `        ``int` `res = ``0``; ` ` `  `        ``// To store count of each ` `        ``// character ` `        ``int``[] count = ``new` `int``[``26``]; ` ` `  `        ``// To store occurrence of each ` `        ``// character ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``count[str.charAt(i) - ``'a'``]++; ` ` `  `        ``// To count characters with odd ` `        ``// occurrence ` `        ``for` `(``int` `i = ``0``; i < ``26``; i++) { ` `            ``if` `(count[i] % ``2` `== ``1``) ` `                ``res++; ` `        ``} ` ` `  `        ``// As one character can be odd return ` `        ``// res - 1 but if string is already ` `        ``// palindrome return 0 ` `        ``return` `(res == ``0``) ? ``0` `: res - ``1``; ` `    ``} ` ` `  `    ``// Driver program ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``String str = ``"geeksforgeeks"``; ` `        ``System.out.println(minInsertion(str)); ` `    ``} ` `} `

## Python3

 `# Python3 program to find minimum number ` `# of insertions to make a string ` `# palindrome ` `import` `math as mt ` ` `  `# Function will return number of ` `# characters to be added ` `def` `minInsertion(tr1): ` ` `  `    ``# To store str1ing length ` `    ``n ``=` `len``(str1) ` ` `  `    ``# To store number of characters ` `    ``# occurring odd number of times ` `    ``res ``=` `0` ` `  `    ``# To store count of each ` `    ``# character ` `    ``count ``=` `[``0` `for` `i ``in` `range``(``26``)] ` ` `  `    ``# To store occurrence of each ` `    ``# character ` `    ``for` `i ``in` `range``(n): ` `        ``count[``ord``(str1[i]) ``-` `ord``(``'a'``)] ``+``=` `1` ` `  `    ``# To count characters with odd ` `    ``# occurrence ` `    ``for` `i ``in` `range``(``26``): ` `        ``if` `(count[i] ``%` `2` `=``=` `1``): ` `            ``res ``+``=` `1` ` `  `    ``# As one character can be odd return ` `    ``# res - 1 but if str1ing is already ` `    ``# palindrome return 0 ` `    ``if` `(res ``=``=` `0``): ` `        ``return` `0` `    ``else``: ` `        ``return` `res ``-` `1` ` `  `# Driver Code ` `str1 ``=` `"geeksforgeeks"` `print``(minInsertion(str1)) ` ` `  `# This code is contributed by  ` `# Mohit kumar 29 `

## C#

 `// C# program to find minimum number ` `// of insertions to make a string ` `// palindrome ` `using` `System; ` ` `  `public` `class` `GFG { ` ` `  `    ``// Function will return number of ` `    ``// characters to be added ` `    ``static` `int` `minInsertion(String str) ` `    ``{ ` `         `  `        ``// To store string length ` `        ``int` `n = str.Length; ` ` `  `        ``// To store number of characters ` `        ``// occurring odd number of times ` `        ``int` `res = 0; ` ` `  `        ``// To store count of each ` `        ``// character ` `        ``int``[] count = ``new` `int``; ` ` `  `        ``// To store occurrence of each ` `        ``// character ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``count[str[i] - ``'a'``]++; ` ` `  `        ``// To count characters with odd ` `        ``// occurrence ` `        ``for` `(``int` `i = 0; i < 26; i++) { ` `            ``if` `(count[i] % 2 == 1) ` `                ``res++; ` `        ``} ` ` `  `        ``// As one character can be odd ` `        ``// return res - 1 but if string ` `        ``// is already palindrome ` `        ``// return 0 ` `        ``return` `(res == 0) ? 0 : res - 1; ` `    ``} ` ` `  `    ``// Driver program ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``string` `str = ``"geeksforgeeks"``; ` `         `  `        ``Console.WriteLine(minInsertion(str)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

## PHP

 ` `

Output:

```2
```