Programa Java para intercambiar caracteres en una string

Dada una String S de longitud N , dos enteros B y C , la tarea es atravesar caracteres comenzando desde el principio, intercambiando un carácter con el carácter después de que C se coloque a partir de él, es decir, intercambiar caracteres en la posición i y (i + C)% n _ Repita este proceso B veces, avanzando una posición a la vez. Su tarea es encontrar la string final después de los intercambios de B.

Ejemplos: 

Input : S = "ABCDEFGH", B = 4, C = 3;
Output:  DEFGBCAH
Explanation:
         after 1st swap: DBCAEFGH
         after 2nd swap: DECABFGH
         after 3rd swap: DEFABCGH
         after 4th swap: DEFGBCAH

Input : S = "ABCDE", B = 10, C = 6;
Output : ADEBC
Explanation:
         after 1st swap: BACDE
         after 2nd swap: BCADE
         after 3rd swap: BCDAE
         after 4th swap: BCDEA
         after 5th swap: ACDEB
         after 6th swap: CADEB
         after 7th swap: CDAEB
         after 8th swap: CDEAB
         after 9th swap: CDEBA
         after 10th swap: ADEBC

Enfoque ingenuo : 

• Para valores grandes de B , el enfoque ingenuo de repetir B veces, cada vez que se intercambia el i-ésimo carácter con (i + C)%N-ésimo carácter dará como resultado un tiempo de CPU elevado.
• El truco para resolver este problema es observar la string resultante después de cada N iteraciones , donde N es la longitud de la string S.
• Nuevamente, si C es mayor o igual que N , es efectivamente igual al resto de C dividido por N.
• En adelante, consideremos que C es menor que N.

Enfoque eficiente: 

• Si observamos la string que se forma después de cada N iteraciones sucesivas e intercambios (llamémoslo una iteración completa), podemos comenzar a obtener un patrón.
• Podemos encontrar que la string se divide en dos partes: la primera parte de longitud C que comprende los primeros caracteres C de S , y la segunda parte que comprende el resto de los caracteres.
• Las dos partes se giran por algunos lugares. La primera parte se gira a la derecha (N % C) coloca cada iteración completa.
• La segunda parte se rota a la izquierda por C coloca cada iteración completa.
• Podemos calcular el número de iteraciones completas f dividiendo B por N .
• Entonces, la primera parte se rotará a la izquierda por ( N ​​% C ) * f . Este valor puede ir más allá de C y, por lo tanto, es efectivamente ( ( N % C ) * f ) % C , es decir, la primera parte se rotará por ( ( N % C ) * f ) % C lugares restantes.
• La segunda parte se rotará a la izquierda C * f lugares. Dado que este valor puede ir más allá de la longitud de la segunda parte que es ( N – C ) , es efectivamente ( ( C * f ) % ( N – C ) ) , es decir, la segunda parte girará en ( ( C * f ) % ( N – C ) ) lugares restantes.
• Después de f iteraciones completas, aún pueden quedar algunas iteraciones para completar B iteraciones. Este valor es B % N que es menor que N . Podemos seguir el enfoque ingenuo en estas iteraciones restantes después de f iteraciones completas para obtener la string resultante.

Ejemplo:
s = ABCDEFGHIJK; c = 4;
partes: ABCD EFGHIJK
después de 1 iteración completa: DABC IJKEFGH 
después de 2 iteraciones completas: CDAB FGHIJKE 
después de 3 iteraciones completas: BCDA JKEFGHI 
después de 4 iteraciones completas: ABCD GHIJKEF 
después de 5 iteraciones completas: DABC KEFGHIJ 
después de 6 iteraciones completas: CDAB HIJKEFG 
después de 7 iteraciones completas : BCDA EFGHIJK 
después de 8 iteraciones completas: ABCD IJKEFGH 
 

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

// Java Program to find new after swapping
// characters at position i and i + c
// b times, each time advancing one
// position ahead
  
class GFG {
    // Method to find the required string
  
    String swapChars(String s, int c, int b)
    {
        // Get string length
        int n = s.length();
  
        // if c is larger or equal to the length of
        // the string is effectively the remainder of
        // c divided by the length of the string
        c = c % n;
  
        if (c == 0) {
            // No change will happen
            return s;
        }
  
        int f = b / n;
        int r = b % n;
  
        // Rotate first c characters by (n % c)
        // places f times
        String p1 = rotateLeft(s.substring(0, c),
                               ((n % c) * f) % c);
  
        // Rotate remaining character by
        // (n * f) places
        String p2 = rotateLeft(s.substring(c),
                               ((c * f) % (n - c)));
  
        // Concatenate the two parts and convert the
        // resultant string formed after f full
        // iterations to a character array
        // (for final swaps)
        char a[] = (p1 + p2).toCharArray();
  
        // Remaining swaps
        for (int i = 0; i < r; i++) {
  
            // Swap ith character with
            // (i + c)th character
            char temp = a[i];
            a[i] = a[(i + c) % n];
            a[(i + c) % n] = temp;
        }
  
        // Return final string
        return new String(a);
    }
  
    String rotateLeft(String s, int p)
    {
        // Rotating a string p times left is
        // effectively cutting the first p
        // characters and placing them at the end
        return s.substring(p) + s.substring(0, p);
    }
  
    // Driver code
    public static void main(String args[])
    {
        // Given values
        String s1 = "ABCDEFGHIJK";
        int b = 1000;
        int c = 3;
  
        // get final string
        String s2 = new GFG().swapChars(s1, c, b);
  
        // print final string
        System.out.println(s2);
    }
}

CADEFGHIJKB

Complejidad de tiempo : O(n) 
Complejidad de espacio : O(n)
 

Consulte el artículo completo sobre el intercambio de caracteres en una string para obtener más detalles.