Print the arranged positions of characters to make palindrome | CPP program to print original positions of characters in a string after rearranging and forming a palindrome ; Maximum number of characters ; Insert all positions of every character in the given string . ; find the number of odd elements . Takes O ( n ) ; A palindrome cannot contain more than 1 odd characters ; Print positions in first half of palindrome ; Consider one instance odd character ; Print positions in second half of palindrome ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 256 ; void printPalindromePos ( string & str ) { vector < int > pos [ MAX ] ; int n = str . length ( ) ; for ( int i = 0 ; i < n ; i ++ ) pos [ str [ i ] ] . push_back ( i + 1 ) ; int oddCount = 0 ; char oddChar ; for ( int i = 0 ; i < MAX ; i ++ ) { if ( pos [ i ] . size ( ) % 2 != 0 ) { oddCount ++ ; oddChar = i ; } } if ( oddCount > 1 ) cout << " NO ▁ PALINDROME " ; for ( int i = 0 ; i < MAX ; i ++ ) { int mid = pos [ i ] . size ( ) / 2 ; for ( int j = 0 ; j < mid ; j ++ ) cout << pos [ i ] [ j ] << " ▁ " ; } if ( oddCount > 0 ) { int last = pos [ oddChar ] . size ( ) - 1 ; cout << pos [ oddChar ] [ last ] << " ▁ " ; pos [ oddChar ] . pop_back ( ) ; } for ( int i = MAX - 1 ; i >= 0 ; i -- ) { int count = pos [ i ] . size ( ) ; for ( int j = count / 2 ; j < count ; j ++ ) cout << pos [ i ] [ j ] << " ▁ " ; } } int main ( ) { string s = " geeksgk " ; printPalindromePos ( s ) ; return 0 ; }