Se le da una string s (solo alfabeto en minúsculas) con longitud n. Imprime la posición de cada carácter de la string que debe adquirir para que forme una string palindrómica.
Ejemplos:
Input : c b b a a Output : 3 1 5 2 4 To make string palindrome 'c' must be at position 3, 'b' at 1 and 5, 'a' at 2 and 4. Input : a b c Output : Not Possible Any permutation of string cannot form palindrome.
La idea es crear una array de vectores (o array de tamaño dinámico) que almacene todas las posiciones de cada carácter. Después de almacenar posiciones, verificamos si el conteo de caracteres impares es más de uno. En caso afirmativo, devolvemos “No es posible”. De lo contrario, primero imprimimos las posiciones de la primera mitad de la array, luego una posición del carácter impar (si está presente) y finalmente las posiciones de la segunda mitad.
C++
// CPP program to print original
// positions of characters in a
// string after rearranging and
// forming a palindrome
#include <bits/stdc++.h>
using namespace std;
// Maximum number of characters
const int MAX = 256;
void printPalindromePos(string &str)
{
// Insert all positions of every
// character in the given string.
vector<int> pos[MAX];
int n = str.length();
for (int i = 0; i < n; i++)
pos[str[i]].push_back(i+1);
/* find the number of odd elements.
Takes O(n) */
int oddCount = 0;
char oddChar;
for (int i=0; i<MAX; i++) {
if (pos[i].size() % 2 != 0) {
oddCount++;
oddChar = i;
}
}
/* A palindrome cannot contain more than 1
odd characters */
if (oddCount > 1)
cout << "NO PALINDROME";
/* Print positions in first half
of 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] << " ";
}
// Consider one instance odd character
if (oddCount > 0)
{
int last = pos[oddChar].size() - 1;
cout << pos[oddChar][last] << " ";
pos[oddChar].pop_back();
}
/* Print positions in second half
of palindrome */
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] << " ";
}
}
// Driver code
int main()
{
string s = "geeksgk";
printPalindromePos(s);
return 0;
}
Java
// JAVA program to print original
// positions of characters in a
// String after rearranging and
// forming a palindrome
import java.util.*;
class GFG
{
// Maximum number of characters
static int MAX = 256;
static void printPalindromePos(String str)
{
// Insert all positions of every
// character in the given String.
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);
/* find the number of odd elements.
Takes O(n) */
int oddCount = 0;
char oddChar = 0;
for (int i = 0; i < MAX; i++)
{
if (pos[i].size() % 2 != 0)
{
oddCount++;
oddChar = (char) i;
}
}
/* A palindrome cannot contain more than 1
odd characters */
if (oddCount > 1)
System.out.print("NO PALINDROME");
/* Print positions in first half
of 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) + " ");
}
// Consider one instance odd character
if (oddCount > 0)
{
int last = pos[oddChar].size() - 1;
System.out.print(pos[oddChar].get(last) + " ");
pos[oddChar].remove(pos[oddChar].size() - 1);
}
/* Print positions in second half
of palindrome */
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) + " ");
}
}
// Driver code
public static void main(String[] args)
{
String s = "geeksgk";
printPalindromePos(s);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to print original
# positions of characters in a
# string after rearranging and
# forming a palindrome
# Maximum number of characters
MAX = 256
def printPalindromePos(Str):
global MAX
# Insert all positions of every
# character in the given string.
pos = [[] for i in range(MAX)]
n = len(Str)
for i in range(n):
pos[ord(Str[i])].append(i+1)
# find the number of odd elements.
# Takes O(n)
oddCount = 0
for i in range(MAX):
if (len(pos[i])% 2 != 0):
oddCount += 1
oddChar = i
# A palindrome cannot contain more than 1
# odd characters
if (oddCount > 1):
print("NO PALINDROME")
# Print positions in first half
# of palindrome
for i in range(MAX):
mid = len(pos[i]) // 2
for j in range(mid):
print(pos[i][j],end = " ")
# Consider one instance odd character
if (oddCount > 0):
last = len(pos[oddChar]) - 1
print(pos[oddChar][last],end = " ")
pos[oddChar].pop()
# Print positions in second half
# of palindrome
for i in range(MAX-1,-1,-1):
count = len(pos[i])
for j in range(count//2,count):
print(pos[i][j],end = " ")
# Driver code
s = "geeksgk"
printPalindromePos(s)
# This code is contributed by shinjanpatra.
C#
// C# program to print original
// positions of characters in a
// String after rearranging and
// forming a palindrome
using System;
using System.Collections.Generic;
class GFG
{
// Maximum number of characters
static int MAX = 256;
static void printPalindromePos(String str)
{
// Insert all positions of every
// character in the given String.
List<int> []pos = new List<int>[MAX];
for (int i = 0; i < MAX; i++)
pos[i] = new List<int>();
int n = str.Length;
for (int i = 0; i < n; i++)
pos[str[i]].Add(i + 1);
/* find the number of odd elements.
Takes O(n) */
int oddCount = 0;
char oddChar = (char)0;
for (int i = 0; i < MAX; i++)
{
if (pos[i].Count % 2 != 0)
{
oddCount++;
oddChar = (char) i;
}
}
/* A palindrome cannot contain more than 1
odd characters */
if (oddCount > 1)
Console.Write("NO PALINDROME");
/* Print positions in first half
of palindrome */
for (int i = 0; i < MAX; i++)
{
int mid = pos[i].Count / 2;
for (int j = 0; j < mid; j++)
Console.Write(pos[i][j] + " ");
}
// Consider one instance odd character
if (oddCount > 0)
{
int last = pos[oddChar].Count - 1;
Console.Write(pos[oddChar][last] + " ");
pos[oddChar].RemoveAt(pos[oddChar].Count - 1);
}
/* Print positions in second half
of palindrome */
for (int i = MAX - 1; i >= 0; i--)
{
int count = pos[i].Count;
for (int j = count / 2; j < count; j++)
Console.Write(pos[i][j] + " ");
}
}
// Driver code
public static void Main(String[] args)
{
String s = "geeksgk";
printPalindromePos(s);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to print original
// positions of characters in a
// string after rearranging and
// forming a palindrome
// Maximum number of characters
var MAX = 256;
function printPalindromePos(str)
{
// Insert all positions of every
// character in the given string.
var pos = Array.from(Array(MAX), ()=>Array());
var n = str.length;
for (var i = 0; i < n; i++)
pos[str[i].charCodeAt(0)].push(i+1);
/* find the number of odd elements.
Takes O(n) */
var oddCount = 0;
var oddChar;
for (var i=0; i<MAX; i++) {
if (pos[i].length % 2 != 0) {
oddCount++;
oddChar = i;
}
}
/* A palindrome cannot contain more than 1
odd characters */
if (oddCount > 1)
document.write( "NO PALINDROME");
/* Print positions in first half
of palindrome */
for (var i=0; i<MAX; i++)
{
var mid = pos[i].length/2;
for (var j=0; j<mid; j++)
document.write( pos[i][j] + " ");
}
// Consider one instance odd character
if (oddCount > 0)
{
var last = pos[oddChar].length - 1;
document.write( pos[oddChar][last] + " ");
pos[oddChar].pop();
}
/* Print positions in second half
of palindrome */
for (var i=MAX-1; i>=0; i--)
{
var count = pos[i].length;
for (var j=count/2; j<count; j++)
document.write( pos[i][j] + " ");
}
}
// Driver code
var s = "geeksgk";
printPalindromePos(s);
</script>
Producción:
2 1 4 5 7 6 3
Tiempo Complejidad : O ( n )
Publicación traducida automáticamente
Artículo escrito por Vaibhav shaw y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA