Dada la string str , la tarea es imprimir el último carácter de la permutación lexicográficamente más pequeña no palindrómica de la string dada . Si no existe tal permutación, imprima “-1” .
Ejemplos:
Entrada: str = “deepqvu”
Salida: v
Explicación: La string “deepquv” es la permutación lexicográficamente más pequeña que no es un palíndromo.
Por lo tanto, el último carácter es v .Entrada: str = “zyxaaabb”
Salida: z
Explicación: La string “aaabbxyz” es la permutación lexicográficamente más pequeña que no es un palíndromo.
Por lo tanto, el último carácter es z .
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las permutaciones posibles de la string dada y, para cada permutación, verificar si es un palíndromo o no. Entre todas las permutaciones no palindrómicas obtenidas, imprime el último carácter de la permutación lexicográficamente más pequeña. Siga los pasos a continuación:
- Ordenar la string dada str .
- Verifique todas las permutaciones posteriores de la string para el palíndromo usando una función next_permutation() .
- Si existe alguna permutación que no sea palindrómica , imprima su último carácter.
- De lo contrario, imprima «-1».
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check whether a string
// s is a palindrome or not
bool isPalin(string s, int N)
{
// Traverse the string
for (int i = 0; i < N; i++) {
// If unequal character
if (s[i] != s[N - i - 1]) {
return false;
}
}
return true;
}
// Function to find the smallest
// non-palindromic lexicographic
// permutation of string s
void lexicographicSmallestString(
string s, int N)
{
// Base Case
if (N == 1) {
cout << "-1";
}
// Sort the given string
sort(s.begin(), s.end());
int flag = 0;
// If the formed string is
// non palindromic
if (isPalin(s, N) == false)
flag = 1;
if (!flag) {
// Check for all permutations
while (next_permutation(s.begin(),
s.end())) {
// Check palindromic
if (isPalin(s, N) == false) {
flag = 1;
break;
}
}
}
// If non palindromic string found
// print its last character
if (flag == 1) {
int lastChar = s.size() - 1;
cout << s[lastChar] << ' ';
}
// Otherwise, print "-1"
else {
cout << "-1";
}
}
// Driver Code
int main()
{
// Given string str
string str = "deepqvu";
// Length of the string
int N = str.length();
// Function Call
lexicographicSmallestString(str, N);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Function to check whether
// a String s is a palindrome
// or not
static boolean isPalin(String s,
int N)
{
// Traverse the String
for (int i = 0; i < N; i++)
{
// If unequal character
if (s.charAt(i) !=
s.charAt(N - i - 1))
{
return false;
}
}
return true;
}
static boolean next_permutation(char[] p)
{
for (int a = p.length - 2;
a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.length - 1;; --b)
if (p[b] > p[a])
{
char t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1;
a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
//Method to sort a string alphabetically
static String sortString(String inputString)
{
// convert input string
// to char array
char tempArray[] =
inputString.toCharArray();
// Sort tempArray
Arrays.sort(tempArray);
// Return new sorted string
return new String(tempArray);
}
// Function to find the smallest
// non-palindromic lexicographic
// permutation of String s
static void lexicographicSmallestString(String s,
int N)
{
// Base Case
if (N == 1)
{
System.out.print("-1");
}
// Sort the given String
s = sortString(s);
int flag = 0;
// If the formed String is
// non palindromic
if (isPalin(s, N) == false)
flag = 1;
if (flag != 0)
{
// Check for all permutations
while (next_permutation(s.toCharArray()))
{
// Check palindromic
if (isPalin(s, N) == false)
{
flag = 1;
break;
}
}
}
// If non palindromic String found
// print its last character
if (flag == 1)
{
int lastChar = s.length() - 1;
System.out.print(s.charAt(lastChar) + " ");
}
// Otherwise, print "-1"
else
{
System.out.print("-1");
}
}
// Driver Code
public static void main(String[] args)
{
// Given String str
String str = "deepqvu";
// Length of the String
int N = str.length();
// Function Call
lexicographicSmallestString(str, N);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the
# above approach
# Function to check whether
# a String s is a palindrome
# or not
def isPalin(s, N):
# Traverse the String
for i in range(N):
# If unequal character
if (s[i] != s[N - i - 1]):
return False;
return True;
def next_permutation(p):
for a in range(len(p) - 2, 0, -1):
if (p[a] < p[a + 1]):
for b in range(len(p) - 1, -1):
if (p[b] > p[a]):
t = p[a];
p[a] = p[b];
p[b] = t;
for a in range(a + 1,
a < b,):
b = len(p) - 1;
if(a < b):
t = p[a];
p[a] = p[b];
p[b] = t;
b -= 1;
return True;
return False;
# Method to sort a string
# alphabetically
def sortString(inputString):
# convert input string
# to char array
# Sort tempArray
tempArray = ''.join(sorted(inputString));
# Return new sorted string
return tempArray;
# Function to find the smallest
# non-palindromic lexicographic
# permutation of String s
def lexicographicSmallestString(s, N):
# Base Case
if (N == 1):
print("-1");
# Sort the given String
s = sortString(s);
flag = 0;
# If the formed String is
# non palindromic
if (isPalin(s, N) == False):
flag = 1;
if (flag != 0):
# Check for all permutations
while (next_permutation(s)):
# Check palindromic
if (isPalin(s, N) == False):
flag = 1;
break;
# If non palindromic String
# found print last character
if (flag == 1):
lastChar = len(s) - 1;
print(s[lastChar],
end = "");
# Otherwise, pr"-1"
else:
print("-1");
# Driver Code
if __name__ == '__main__':
# Given String str
str = "deepqvu";
# Length of the String
N = len(str);
# Function Call
lexicographicSmallestString(str, N);
# This code is contributed by shikhasingrajput
C#
// C# program for the
// above approach
using System;
class GFG{
// Function to check whether
// a String s is a palindrome
// or not
static bool isPalin(String s,
int N)
{
// Traverse the String
for (int i = 0; i < N; i++)
{
// If unequal character
if (s[i] !=
s[N - i - 1])
{
return false;
}
}
return true;
}
static bool next_permutation(char[] p)
{
for (int a = p.Length - 2;
a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.Length - 1;; --b)
if (p[b] > p[a])
{
char t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.Length - 1;
a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
//Method to sort a string alphabetically
static String sortString(String inputString)
{
// convert input string
// to char array
char []tempArray =
inputString.ToCharArray();
// Sort tempArray
Array.Sort(tempArray);
// Return new sorted string
return new String(tempArray);
}
// Function to find the smallest
// non-palindromic lexicographic
// permutation of String s
static void lexicographicSmallestString(String s,
int N)
{
// Base Case
if (N == 1)
{
Console.Write("-1");
}
// Sort the given String
s = sortString(s);
int flag = 0;
// If the formed String is
// non palindromic
if (isPalin(s, N) == false)
flag = 1;
if (flag != 0)
{
// Check for all permutations
while (next_permutation(s.ToCharArray()))
{
// Check palindromic
if (isPalin(s, N) == false)
{
flag = 1;
break;
}
}
}
// If non palindromic String found
// print its last character
if (flag == 1)
{
int lastChar = s.Length - 1;
Console.Write(s[lastChar] + " ");
}
// Otherwise, print "-1"
else
{
Console.Write("-1");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given String str
String str = "deepqvu";
// Length of the String
int N = str.Length;
// Function Call
lexicographicSmallestString(str, N);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the
// above approach
// Function to check whether
// a String s is a palindrome
// or not
function isPalin(s, N) {
// Traverse the String
for (var i = 0; i < N; i++) {
// If unequal character
if (s[i] !== s[N - i - 1]) {
return false;
}
}
return true;
}
function next_permutation(p) {
for (var a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (var b = p.length - 1; ; --b)
if (p[b] > p[a]) {
var t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
//Method to sort a string alphabetically
function sortString(inputString) {
// convert input string
// to char array
var tempArray = inputString.split("");
// Sort tempArray
tempArray.sort();
// Return new sorted string
return tempArray.join("");
}
// Function to find the smallest
// non-palindromic lexicographic
// permutation of String s
function lexicographicSmallestString(s, N) {
// Base Case
if (N === 1) {
document.write("-1");
}
// Sort the given String
s = sortString(s);
var flag = 0;
// If the formed String is
// non palindromic
if (isPalin(s, N) === false) flag = 1;
if (flag !== 0) {
// Check for all permutations
while (next_permutation(s.split(""))) {
// Check palindromic
if (isPalin(s, N) === false) {
flag = 1;
break;
}
}
}
// If non palindromic String found
// print its last character
if (flag === 1) {
var lastChar = s.length - 1;
document.write(s[lastChar] + " ");
}
// Otherwise, print "-1"
else {
document.write("-1");
}
}
// Driver Code
// Given String str
var str = "deepqvu";
// Length of the String
var N = str.length;
// Function Call
lexicographicSmallestString(str, N);
</script>
Producción
v
Complejidad temporal: O(N*N!)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es almacenar las frecuencias de cada carácter de la string dada str . Si todos los caracteres son iguales, imprima “-1” . De lo contrario, imprima el carácter más grande de la string dada str .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the smallest non
// palindromic lexicographic string
void lexicographicSmallestString(
string s, int N)
{
// Stores the frequency of each
// character of the string s
map<char, int> M;
// Traverse the string
for (char ch : s) {
M[ch]++;
}
// If there is only one element
if (M.size() == 1) {
cout << "-1";
}
// Otherwise
else {
auto it = M.rbegin();
cout << it->first;
}
}
// Driver Code
int main()
{
// Given string str
string str = "deepqvu";
// Length of the string
int N = str.length();
// Function Call
lexicographicSmallestString(str, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to find the smallest non
// palindromic lexicographic string
static void lexicographicSmallestString(String s,
int N)
{
// Stores the frequency of each
// character of the string s
SortedMap<Character,
Integer> M = new TreeMap<Character,
Integer>();
// Converting given string to char array
char[] str = s.toCharArray();
// Traverse the string
for(char c : str)
{
if (M.containsKey(c))
{
// If char is present in M
M.put(c, M.get(c) + 1);
}
else
{
// If char is not present in M
M.put(c, 1);
}
}
// If there is only one element
if (M.size() == 1)
{
System.out.print("-1");
}
// Otherwise
else
{
System.out.print( M.lastKey() );
}
}
// Driver Code
public static void main (String[] args)
{
// Given string str
String str = "deepqvu";
// Length of the string
int N = str.length();
// Function Call
lexicographicSmallestString(str, N);
}
}
// This code is contributed by math_lover
Python3
# Python3 program for the above approach
# Function to find the smallest non
# palindromic lexicographic string
def lexicographicSmallestString(s, N):
# Stores the frequency of each
# character of the s
M = {}
# Traverse the string
for ch in s:
M[ch] = M.get(ch, 0) + 1
# If there is only one element
if len(M) == 1:
print("-1")
# Otherwise
else:
x = list(M.keys())[-2]
print(x)
# Driver Code
if __name__ == '__main__':
# Given str
str = "deepqvu"
# Length of the string
N = len(str)
# Function call
lexicographicSmallestString(str, N)
# This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the smallest non
// palindromic lexicographic string
static void lexicographicSmallestString(String s,
int N)
{
// Stores the frequency of each
// character of the string s
SortedDictionary<char,
int> M = new SortedDictionary<char,
int>();
// Converting given string
// to char array
char[] str = s.ToCharArray();
// Traverse the string
foreach(char c in str)
{
if (M.ContainsKey(c))
{
// If char is present
// in M
M = M + 1;
}
else
{
// If char is not present
// in M
M.Add(c, 1);
}
}
// If there is only
// one element
if (M.Count == 1)
{
Console.Write("-1");
}
// Otherwise
else
{
int count = 0;
foreach(KeyValuePair<char,
int> m in M)
{
count++;
if(count == M.Count)
Console.Write(m.Key);
}
}
}
// Driver Code
public static void Main(String[] args)
{
// Given string str
String str = "deepqvu";
// Length of the string
int N = str.Length;
// Function Call
lexicographicSmallestString(str, N);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Function to find the smallest non
// palindromic lexicographic string
function lexicographicSmallestString(s,N)
{
// Stores the frequency of each
// character of the string s
let M = new Map();
// Converting given string to char array
let str = s.split("");
// Traverse the string
for(let c=0;c< str.length;c++)
{
if (M.has(str))
{
// If char is present in M
M.set(str, M.get(str) + 1);
}
else
{
// If char is not present in M
M.set(str, 1);
}
}
// If there is only one element
if (M.size == 1)
{
document.write("-1");
}
// Otherwise
else
{
let temp=Array.from(M)
document.write( temp[temp.length-2][0] );
}
}
// Driver Code
let str = "deepqvu";
let N = str.length;
// Function Call
lexicographicSmallestString(str, N);
// This code is contributed by patel2127
</script>
Producción
v
Complejidad temporal: O(N)
Espacio auxiliar: O(26)
Publicación traducida automáticamente
Artículo escrito por crisscross y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA