Encuentre un anagrama de una string dada que tenga diferentes caracteres en los índices correspondientes

Dada una string S que consta de N caracteres, la tarea es encontrar el anagrama de la string S tal que los caracteres en los mismos índices sean diferentes de la string original.

Ejemplos:

Entrada: S = «geek»
Salida: egke
Explicación:
El anagrama de la string dada tal que todos los caracteres en todos los índices correspondientes no son iguales es «egke».  

Entrada: S = “ aaaa”
Salida: -1

Enfoque: El problema dado se puede resolver utilizando el enfoque de dos punteros . La idea es intercambiar los diferentes caracteres al final de la string y si los caracteres en esos índices son los mismos, entonces verifique los siguientes pares posibles de índices que tengan diferentes caracteres. Después de realizar las operaciones anteriores, verifique si el anagrama generó caracteres diferentes en cada índice o no e imprima el resultado en consecuencia. Siga los pasos a continuación para resolver el problema dado:

• Inicializa una string, digamos T que almacena la string S dada .
• Inicialice dos punteros, digamos i  y j como 0 y (N – 1) respectivamente.
• Iterar hasta que el valor de i sea menor que N y j no sea negativo y realizar los siguientes pasos:
  1. Si los caracteres S[i] y S[j] no son iguales y los pares de caracteres (S[i], T[j]) y (T[i], S[j]) tampoco son iguales( eso asegura que los caracteres después de la operación de intercambio sean los mismos que los originales), luego intercambie los caracteres (S[i], S[j]) y actualice el valor de j a (N – 1) .
  2. De lo contrario, incrementa el valor de i en 1 .
• Si la string tiene un número impar de caracteres y los caracteres en los índices intermedios son iguales, realice la operación de intercambio como se ilustra en los pasos anteriores.
• Después de completar los pasos anteriores, si los caracteres en los índices correspondientes de la string S y T no son iguales, imprima la string S como la string resultante. De lo contrario, imprima «-1» .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find anagram of string
// such that characters at the same
// indices are different
void findAnagram(string s)
{
    // Copying our original string
    // for comparison
    string check = s;
 
    // Declaring the two pointers
    int i = 0, j = s.length() - 1;
 
    while (i < s.length() && j >= 0) {
 
        // Checking the given condition
        if (s[i] != s[j] && check[i] != s[j]
            && check[j] != s[i]) {
            swap(s[i], s[j]);
            i++;
 
            j = s.length() - 1;
        }
        else {
            j--;
        }
    }
 
    // When string length is odd
    if (s.length() % 2 != 0) {
 
        // The mid element
        int mid = s.length() / 2;
 
        // If the characters are the
        // same, then perform the swap
        // operation as illustrated
        if (check[mid] == s[mid]) {
            for (int i = 0; i < s.length(); i++) {
                if (check[i] != s[mid]
                    && s[i] != s[mid]) {
                    swap(s[i], s[mid]);
                    break;
                }
            }
        }
    }
 
    // Check if the corresponding indices
    // has the same character or not
    bool ok = true;
    for (int i = 0; i < s.length(); i++) {
        if (check[i] == s[i]) {
            ok = false;
            break;
        }
    }
 
    // If string follows required
    // condition
    if (ok)
        cout << s;
    else
        cout << -1;
}
 
// Driver Code
int main()
{
    string S = "geek";
    findAnagram(S);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG {
 
// Function to find anagram of string
// such that characters at the same
// indices are different
static void findAnagram(String s)
{
    
    // Copying our original string
    // for comparison
    String check = s;
  
    // Declaring the two pointers
    int i = 0, j = s.length() - 1;
  
    while (i < s.length() && j >= 0) {
  
        // Checking the given condition
        if (s.charAt(i) != s.charAt(j) && check.charAt(i) != s.charAt(j)
            && check.charAt(j) != s.charAt(i)) {
            char temp = s.charAt(i);
            s = s.substring(0, i) + s.charAt(j) + s.substring(i + 1);
            s = s.substring(0, j) + temp + s.substring(j + 1);
            i++;
  
            j = s.length() - 1;
        }
        else {
            j--;
        }
    }
  
    // When string length is odd
    if (s.length() % 2 != 0) {
  
        // The mid element
        int mid = s.length() / 2;
  
        // If the characters are the
        // same, then perform the swap
        // operation as illustrated
        if (check.charAt(mid) == s.charAt(mid)) {
            for (i = 0; i < s.length(); i++) {
                if (check.charAt(i) != s.charAt(mid)
                    && s.charAt(i) != s.charAt(mid)) {
                    char temp = s.charAt(i);
                    s = s.substring(0, i) + s.charAt(mid) + s.substring(i + 1);
                    s = s.substring(0, mid) + temp + s.substring(mid + 1);
                    break;
                }
            }
        }
    }
  
    // Check if the corresponding indices
    // has the same character or not
    boolean ok = true;
     
    for (i = 0; i < s.length(); i++) {
        if (check.charAt(i) == s.charAt(i) ) {
            ok = false;
            break;
        }
    }
  
    // If string follows required
    // condition
    if (ok)
        System.out.println(s);
    else
        System.out.println(-1);
}
 
// Driver Code
public static void main (String[] args)
{
    String S = "geek";
    findAnagram(S);
}
}
 
// This code is contributed by sanjoy_62.

# Python 3 program for the above approach
 
# Function to find anagram of string
# such that characters at the same
# indices are different
def findAnagram(s):
 
    # Copying our original string
    # for comparison
    check = s
    st = list(s)
 
    # Declaring the two pointers
    i = 0
    j = len(st) - 1
 
    while (i < len(st) and j >= 0):
 
        # Checking the given condition
        if (st[i] != st[j] and check[i] != st[j]
                and check[j] != st[i]):
            st[i], st[j] = st[j], st[i]
            i += 1
 
            j = len(st) - 1
 
        else:
            j -= 1
 
    # When string length is odd
    if (len(st) % 2 != 0):
 
        # The mid element
        mid = len(st) / 2
 
        # If the characters are the
        # same, then perform the swap
        # operation as illustrated
        if (check[mid] == st[mid]):
            for i in range(len(st)):
                if (check[i] != st[mid]
                        and st[i] != st[mid]):
                    st[i], st[mid] = st[mid], st[i]
                    break
 
    # Check if the corresponding indices
    # has the same character or not
    ok = True
    for i in range(len(st)):
        if (check[i] == st[i]):
            ok = False
            break
 
    # If string follows required
    # condition
    if (ok):
        print("".join(st))
    else:
        print(-1)
 
# Driver Code
if __name__ == "__main__":
 
    S = "geek"
    findAnagram(S)
 
    # This code is contributed by ukasp.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find anagram of string
// such that characters at the same
// indices are different
static void findAnagram(string s)
{
   
    // Copying our original string
    // for comparison
    string check = s;
 
    // Declaring the two pointers
    int i = 0, j = s.Length - 1;
 
    while (i < s.Length && j >= 0) {
 
        // Checking the given condition
        if (s[i] != s[j] && check[i] != s[j]
            && check[j] != s[i]) {
            char temp = s[i];
            s = s.Substring(0, i) + s[j] + s.Substring(i + 1);
            s = s.Substring(0, j) + temp + s.Substring(j + 1);
            i++;
 
            j = s.Length - 1;
        }
        else {
            j--;
        }
    }
 
    // When string length is odd
    if (s.Length % 2 != 0) {
 
        // The mid element
        int mid = s.Length / 2;
 
        // If the characters are the
        // same, then perform the swap
        // operation as illustrated
        if (check[mid] == s[mid]) {
            for (i = 0; i < s.Length; i++) {
                if (check[i] != s[mid]
                    && s[i] != s[mid]) {
                    char temp = s[i];
                    s = s.Substring(0, i) + s[mid] + s.Substring(i + 1);
                    s = s.Substring(0, mid) + temp + s.Substring(mid + 1);
                    break;
                }
            }
        }
    }
 
    // Check if the corresponding indices
    // has the same character or not
    bool ok = true;
    for (i = 0; i < s.Length; i++) {
        if (check[i] == s[i]) {
            ok = false;
            break;
        }
    }
 
    // If string follows required
    // condition
    if (ok)
        Console.Write(s);
    else
        Console.Write(-1);
}
 
// Driver Code
public static void Main()
{
    string S = "geek";
    findAnagram(S);
}
}
 
// This code is contributed by ipg2016107.

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to find anagram of string
        // such that characters at the same
        // indices are different
        function swap(str, i, j) {
            if (i == j) {
                return str;
            }
 
            if (j < i) {
                var temp = j;
                j = i;
                i = temp;
            }
 
            if (i >= str.length) {
                return str;
 
            }
            return str.substring(0, i) +
                str[j] +
 
                str.substring(i + 1, j) +
 
                str[i] +
                str.substring(j + 1);
        }
 
        function findAnagram(s)
        {
         
            // Copying our original string
            // for comparison
            let check = s.slice();
 
            // Declaring the two pointers
            let i = 0, j = s.length - 1;
 
            while (i < s.length && j >= 0) {
 
                // Checking the given condition
                if (s[i] != s[j] && check[i] != s[j]
                    && check[j] != s[i]) {
                    s = swap(s, i, j)
                    i++;
 
                    j = s.length - 1;
                }
                else {
                    j--;
                }
            }
 
            // When string length is odd
            if (s.length % 2 != 0) {
 
                // The mid element
                let mid = s.length / 2;
 
                // If the characters are the
                // same, then perform the swap
                // operation as illustrated
                if (check[mid] == s[mid]) {
                    for (let i = 0; i < s.length; i++) {
                        if (check[i] != s[mid]
                            && s[i] != s[mid]) {
                            s = swap(s, i, mid)
                            break;
                        }
                    }
                }
            }
             
            // Check if the corresponding indices
            // has the same character or not
            let ok = true;
            for (let i = 0; i < s.length; i++) {
                if (check[i] == s[i]) {
                    ok = false;
                    break;
                }
            }
 
            // If string follows required
            // condition
            if (ok)
                document.write(s);
            else
                document.write(-1);
        }
 
        // Driver Code
 
        let S = "geek";
        findAnagram(S);
 
// This code is contributed by Potta Lokesh
    </script>

egke

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)