Dada una string ordenada S que consta de N caracteres en minúscula, la tarea es reorganizar los caracteres en la string dada de modo que no haya dos caracteres adyacentes iguales. Si no es posible reorganizar según los criterios dados, imprima «-1» .
Ejemplos:
Entrada: S = “aaabc”
Salida: abacáEntrada: S = “aa”
Salida: -1
Enfoque: El problema dado se puede resolver utilizando la técnica de dos puntos . Siga los pasos a continuación para resolver este problema:
- Itere sobre los caracteres de la string S y verifique si no hay dos caracteres adyacentes iguales en la string y luego imprima la string S .
- De lo contrario, si el tamaño de la string es 2 y tiene los mismos caracteres, imprima «-1» .
- Inicialice tres variables, por ejemplo, i como 0 , j como 1 y k como 2 para atravesar la string S.
- Iterar mientras k es menor que N y realizar los siguientes pasos:
- Si S[i] no es igual a S[j] , entonces incremente i y j en 1 , e incremente k en 1 , si el valor de j es igual a k .
- De lo contrario, si S[j] es igual a S[k] , incremente k en 1 .
- De lo contrario, intercambie s[j] y s[k] e incremente i y j en 1 , y si j es igual a k, entonces incremente k en 1 .
- Después de completar los pasos anteriores, invierta la string S .
- Finalmente, itere sobre los caracteres de la string S y verifique si no hay dos caracteres adyacentes iguales. Si se encuentra que es cierto , imprima la string S . 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 if a string S
// contains pair of adjacent
// characters that are equal or not
bool isAdjChar(string& s)
{
// Traverse the string S
for (int i = 0; i < s.size() - 1; i++) {
// If S[i] and S[i+1] are equal
if (s[i] == s[i + 1])
return true;
}
// Otherwise, return false
return false;
}
// Function to rearrange characters
// of a string such that no pair of
// adjacent characters are the same
void rearrangeStringUtil(string& S, int N)
{
// Initialize 3 variables
int i = 0, j = 1, k = 2;
// Iterate until k < N
while (k < N) {
// If S[i] is not equal
// to S[j]
if (S[i] != S[j]) {
// Increment i and j by 1
i++;
j++;
// If j equals k and increment
// the value of K by 1
if (j == k) {
k++;
}
}
// Else
else {
// If S[j] equals S[k]
if (S[j] == S[k]) {
// Increment k by 1
k++;
}
// Else
else {
// Swap
swap(S[k], S[j]);
// Increment i and j
// by 1
i++;
j++;
// If j equals k
if (j == k) {
// Increment k by 1
k++;
}
}
}
}
}
// Function to rearrange characters
// in a string so that no two
// adjacent characters are same
string rearrangeString(string& S, int N)
{
// If string is already valid
if (isAdjChar(S) == false) {
return S;
}
// If size of the string is 2
if (S.size() == 2)
return "-1";
// Function Call
rearrangeStringUtil(S, N);
// Reversing the string
reverse(S.begin(), S.end());
// Function Call
rearrangeStringUtil(S, N);
// If the string is valid
if (isAdjChar(S) == false) {
return S;
}
// Otherwise
return "-1";
}
// Driver Code
int main()
{
string S = "aaabc";
int N = S.length();
cout << rearrangeString(S, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
static char []S = "aaabc".toCharArray();
// Function to check if a String S
// contains pair of adjacent
// characters that are equal or not
static boolean isAdjChar()
{
// Traverse the String S
for (int i = 0; i < S.length - 1; i++)
{
// If S[i] and S[i+1] are equal
if (S[i] == S[i + 1])
return true;
}
// Otherwise, return false
return false;
}
// Function to rearrange characters
// of a String such that no pair of
// adjacent characters are the same
static void rearrangeStringUtil(int N)
{
// Initialize 3 variables
int i = 0, j = 1, k = 2;
// Iterate until k < N
while (k < N) {
// If S[i] is not equal
// to S[j]
if (S[i] != S[j]) {
// Increment i and j by 1
i++;
j++;
// If j equals k and increment
// the value of K by 1
if (j == k) {
k++;
}
}
// Else
else {
// If S[j] equals S[k]
if (S[j] == S[k]) {
// Increment k by 1
k++;
}
// Else
else {
// Swap
swap(k,j);
// Increment i and j
// by 1
i++;
j++;
// If j equals k
if (j == k) {
// Increment k by 1
k++;
}
}
}
}
}
static void swap(int i, int j)
{
char temp = S[i];
S[i] = S[j];
S[j] = temp;
}
// Function to rearrange characters
// in a String so that no two
// adjacent characters are same
static String rearrangeString(int N)
{
// If String is already valid
if (isAdjChar() == false) {
return String.valueOf(S);
}
// If size of the String is 2
if (S.length == 2)
return "-1";
// Function Call
rearrangeStringUtil(N);
// Reversing the String
reverse();
// Function Call
rearrangeStringUtil(N);
// If the String is valid
if (isAdjChar() == false) {
return String.valueOf(S);
}
// Otherwise
return "-1";
}
static void reverse() {
int l, r = S.length - 1;
for (l = 0; l < r; l++, r--) {
char temp = S[l];
S[l] = S[r];
S[r] = temp;
}
}
// Driver Code
public static void main(String[] args)
{
int N = S.length;
System.out.print(rearrangeString(N));
}
}
// This code is contributed by Princi Singh
Python3
# Python 3 program for the above approach S = "aaabc" # Function to check if a string S # contains pair of adjacent # characters that are equal or not def isAdjChar(s): # Traverse the string S for i in range(len(s)-1): # If S[i] and S[i+1] are equal if (s[i] == s[i + 1]): return True # Otherwise, return false return False # Function to rearrange characters # of a string such that no pair of # adjacent characters are the same def rearrangeStringUtil(N): global S S = list(S) # Initialize 3 variables i = 0 j = 1 k = 2 # Iterate until k < N while (k < N): # If S[i] is not equal # to S[j] if (S[i] != S[j]): # Increment i and j by 1 i += 1 j += 1 # If j equals k and increment # the value of K by 1 if (j == k): k += 1 # Else else: # If S[j] equals S[k] if (S[j] == S[k]): # Increment k by 1 k += 1 # Else else: # Swap temp = S[k] S[k] = S[j] S[j] = temp # Increment i and j # by 1 i += 1 j += 1 # If j equals k if (j == k): # Increment k by 1 k += 1 S = ''.join(S) # Function to rearrange characters # in a string so that no two # adjacent characters are same def rearrangeString(N): global S # If string is already valid if (isAdjChar(S) == False): return S # If size of the string is 2 if (len(S) == 2): return "-1" # Function Call rearrangeStringUtil(N) # Reversing the string S = S[::-1] # Function Call rearrangeStringUtil(N) # If the string is valid if (isAdjChar(S) == False): return S # Otherwise return "-1" # Driver Code if __name__ == '__main__': N = len(S) print(rearrangeString(N)) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
public class GFG
{
static char []S = "aaabc".ToCharArray();
// Function to check if a String S
// contains pair of adjacent
// characters that are equal or not
static bool isAdjChar()
{
// Traverse the String S
for (int i = 0; i < S.Length - 1; i++)
{
// If S[i] and S[i+1] are equal
if (S[i] == S[i + 1])
return true;
}
// Otherwise, return false
return false;
}
// Function to rearrange characters
// of a String such that no pair of
// adjacent characters are the same
static void rearrangeStringUtil(int N)
{
// Initialize 3 variables
int i = 0, j = 1, k = 2;
// Iterate until k < N
while (k < N) {
// If S[i] is not equal
// to S[j]
if (S[i] != S[j]) {
// Increment i and j by 1
i++;
j++;
// If j equals k and increment
// the value of K by 1
if (j == k) {
k++;
}
}
// Else
else {
// If S[j] equals S[k]
if (S[j] == S[k]) {
// Increment k by 1
k++;
}
// Else
else {
// Swap
swap(k,j);
// Increment i and j
// by 1
i++;
j++;
// If j equals k
if (j == k) {
// Increment k by 1
k++;
}
}
}
}
}
static void swap(int i, int j)
{
char temp = S[i];
S[i] = S[j];
S[j] = temp;
}
// Function to rearrange characters
// in a String so that no two
// adjacent characters are same
static String rearrangeString(int N)
{
// If String is already valid
if (isAdjChar() == false) {
return String.Join("",S);
}
// If size of the String is 2
if (S.Length == 2)
return "-1";
// Function Call
rearrangeStringUtil(N);
// Reversing the String
reverse();
// Function Call
rearrangeStringUtil(N);
// If the String is valid
if (isAdjChar() == false) {
return String.Join("",S);
}
// Otherwise
return "-1";
}
static void reverse() {
int l, r = S.Length - 1;
for (l = 0; l < r; l++, r--) {
char temp = S[l];
S[l] = S[r];
S[r] = temp;
}
}
// Driver Code
public static void Main(String[] args)
{
int N = S.Length;
Console.Write(rearrangeString(N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for the above approach
let S = "aaabc"
// Function to check if a string S
// contains pair of adjacent
// characters that are equal or not
function isAdjChar(s){
// Traverse the string S
for(let i = 0; i < s.length - 1; i++){
// If S[i] and S[i+1] are equal
if (s[i] == s[i + 1])
return true
}
// Otherwise, return false
return false
}
// Function to rearrange characters
// of a string such that no pair of
// adjacent characters are the same
function rearrangeStringUtil(N){
S = S.split("")
// Initialize 3 variables
let i = 0
let j = 1
let k = 2
// Iterate until k < N
while (k < N){
// If S[i] is not equal
// to S[j]
if (S[i] != S[j]){
// Increment i and j by 1
i += 1
j += 1
// If j equals k and increment
// the value of K by 1
if (j == k)
k += 1
}
// Else
else{
// If S[j] equals S[k]
if (S[j] == S[k]){
// Increment k by 1
k += 1
}
// Else
else{
// Swap
let temp = S[k]
S[k] = S[j]
S[j] = temp
// Increment i and j
// by 1
i += 1
j += 1
// If j equals k
if (j == k){
// Increment k by 1
k += 1
}
}
}
}
S = S.join('')
}
// Function to rearrange characters
// in a string so that no two
// adjacent characters are same
function rearrangeString(N){
// If string is already valid
if (isAdjChar(S) == false)
return S
// If size of the string is 2
if (S.length == 2)
return "-1"
// Function Call
rearrangeStringUtil(N)
// Reversing the string
S = S.split("").reverse().join("")
// Function Call
rearrangeStringUtil(N)
// If the string is valid
if (isAdjChar(S) == false)
return S
// Otherwise
return "-1"
}
// Driver Code
let N = S.length;
document.write(rearrangeString(N))
// This code is contributed by shinjanpatra
</script>
Producción:
acaba
Complejidad de tiempo: O (N), ya que estamos usando la función inversa que costará O (N) tiempo.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por raunakrathour y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA