Print the arranged positions of characters to make palindrome | JAVA 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
import java . util . * ; class GFG { static int MAX = 256 ; static void printPalindromePos ( String str ) { Vector < Integer > [ ] pos = new Vector [ MAX ] ; for ( int i = 0 ; i < MAX ; i ++ ) pos [ i ] = new Vector < Integer > ( ) ; int n = str . length ( ) ; for ( int i = 0 ; i < n ; i ++ ) pos [ str . charAt ( i ) ] . add ( i + 1 ) ; int oddCount = 0 ; char oddChar = 0 ; for ( int i = 0 ; i < MAX ; i ++ ) { if ( pos [ i ] . size ( ) % 2 != 0 ) { oddCount ++ ; oddChar = ( char ) i ; } } if ( oddCount > 1 ) System . out . print ( " NO ▁ PALINDROME " ) ; for ( int i = 0 ; i < MAX ; i ++ ) { int mid = pos [ i ] . size ( ) / 2 ; for ( int j = 0 ; j < mid ; j ++ ) System . out . print ( pos [ i ] . get ( j ) + " ▁ " ) ; } if ( oddCount > 0 ) { int last = pos [ oddChar ] . size ( ) - 1 ; System . out . print ( pos [ oddChar ] . get ( last ) + " ▁ " ) ; pos [ oddChar ] . remove ( pos [ oddChar ] . size ( ) - 1 ) ; } for ( int i = MAX - 1 ; i >= 0 ; i -- ) { int count = pos [ i ] . size ( ) ; for ( int j = count / 2 ; j < count ; j ++ ) System . out . print ( pos [ i ] . get ( j ) + " ▁ " ) ; } } public static void main ( String [ ] args ) { String s = " geeksgk " ; printPalindromePos ( s ) ; } }