Mueva todas las ocurrencias de la letra ‘x’ desde la string s hasta el final usando Recursion

Dada una string s , nuestra tarea es mover todas las ocurrencias de la letra x al final de la string s usando recursividad.
Nota: Si solo hay una letra x en la string dada, devuelva la string sin cambios.

Ejemplos: 

Entrada: s= “geekxsforgexxeksxx” 
Salida: geeksforgeeksxxxxx 
Explicación: 
Todas las apariciones de la letra ‘x’ se mueven al final.

Entrada: s = “xxxxx” 
Salida: xxxxx 
Explicación: 
Dado que solo hay una letra x en la string dada, la salida no se modifica. 
 

Enfoque:
Para resolver el problema mencionado anteriormente podemos usar Recursión . Recorra la string y verifique recursivamente si el carácter actual es igual al carácter ‘x’ o no. De lo contrario, imprima el carácter; de lo contrario, pase al siguiente carácter hasta alcanzar la longitud de la string s.

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

// C++ implementation to Move all occurrence of letter ‘x’
// from the string s to the end using Recursion
#include <bits/stdc++.h>
using namespace std;
 
// Function to move all 'x' in the end
void moveAtEnd(string s, int i, int l)
{
    if (i >= l)
        return;
 
    // Store current character
    char curr = s[i];
 
    // Check if current character is not 'x'
    if (curr != 'x')
        cout << curr;
 
    // recursive function call
    moveAtEnd(s, i + 1, l);
 
    // Check if current character is 'x'
    if (curr == 'x')
        cout << curr;
 
    return;
}
 
// Driver code
int main()
{
    string s = "geekxsforgexxeksxx";
 
    int l = s.length();
 
    moveAtEnd(s, 0, l);
 
    return 0;
}

// Java implementation to Move all occurrence of letter ‘x’
// from the string s to the end using Recursion
import java.util.*;
class GFG{
 
// Function to move all 'x' in the end
static void moveAtEnd(String s, int i, int l)
{
    if (i >= l)
        return;
 
    // Store current character
    char curr = s.charAt(i);
 
    // Check if current character is not 'x'
    if (curr != 'x')
        System.out.print(curr);
 
    // recursive function call
    moveAtEnd(s, i + 1, l);
 
    // Check if current character is 'x'
    if (curr == 'x')
        System.out.print(curr);
 
    return;
}
 
// Driver code
public static void main(String args[])
{
    String s = "geekxsforgexxeksxx";
 
    int l = s.length();
 
    moveAtEnd(s, 0, l);
}
}
 
// This code is contributed by Code_Mech

# Python3 implementation to move all
# occurrences of letter ‘x’ from the
# string s to the end using recursion
 
# Function to move all 'x' in the end
def moveAtEnd(s, i, l):
 
    if(i >= l):
       return
 
    # Store current character
    curr = s[i]
 
    # Check if current character
    # is not 'x'
    if(curr != 'x'):
        print(curr, end = "")
 
    # Recursive function call
    moveAtEnd(s, i + 1, l)
 
    # Check if current character is 'x'
    if(curr == 'x'):
        print(curr, end = "")
 
    return
 
# Driver code
if __name__ == '__main__':
 
    s = "geekxsforgexxeksxx"
    l = len(s)
 
    moveAtEnd(s, 0, l)
 
# This code is contributed by Shivam Singh

// C# implementation to Move all occurrence of letter ‘x’
// from the string s to the end using Recursion
using System;
class GFG{
 
// Function to move all 'x' in the end
static void moveAtEnd(string s, int i, int l)
{
    if (i >= l)
        return;
 
    // Store current character
    char curr = s[i];
 
    // Check if current character is not 'x'
    if (curr != 'x')
        Console.Write(curr);
 
    // recursive function call
    moveAtEnd(s, i + 1, l);
 
    // Check if current character is 'x'
    if (curr == 'x')
        Console.Write(curr);
 
    return;
}
 
// Driver code
public static void Main()
{
    string s = "geekxsforgexxeksxx";
 
    int l = s.Length;
 
    moveAtEnd(s, 0, l);
}
}
 
// This code is contributed by Nidhi_Biet

<script>
 
// Javascript implementation to Move
// all occurrence of letter ‘x’ from
// the string s to the end using Recursion
 
// Function to move all 'x' in the end
function moveAtEnd(s, i, l)
{
    if (i >= l)
        return;
 
    // Store current character
    let curr = s[i];
 
    // Check if current character is not 'x'
    if (curr != 'x')
        document.write(curr);
 
    // Recursive function call
    moveAtEnd(s, i + 1, l);
 
    // Check if current character is 'x'
    if (curr == 'x')
        document.write(curr);
 
    return;
}
 
// Driver code
let s = "geekxsforgexxeksxx";
let l = s.length;
 
moveAtEnd(s, 0, l);
 
// This code is contributed by suresh07
 
</script>

geeksforgeeksxxxxx

Complejidad de tiempo: O(n), donde n es la longitud de la string dada.

Otra implementación que implica el intercambio de caracteres:

En este enfoque, intercambiaremos caracteres adyacentes para traer ‘x’ al final.

A continuación se muestra la implementación de la técnica anterior:

// C++ program for above approach
#include<bits/stdc++.h>
using namespace std;
 
// Recursive program to bring 'x'
// to the end
void rec(char *a, int i)
{
     
    // When the string is completed
    // from reverse direction end of recursion
    if(i == 0)
    {
      cout << a << endl;
      return;
    }
   
    // If the character x is found
    if(a[i] == 'x')
    {
       
      // Transverse the whole string
      int j = i;
      while(a[j] != '\0' && a[j+1] != '\0')
      {
         
        // Swap the x so that
        // it moves to the last
        swap(a[j], a[j+1]);
        j++;
      }
    }
   
    // call to the smaller problem now
    rec(a, i - 1);
}
 
// Driver Code
int main()
{
    char a[] = {'g', 'e', 'e', 'k', 'x',
            's', 'x', 'x', 'k', 's', '\0'};
     
    // Size of a
    int n = 10;
   
    // Call to rec
    rec(a,n-1);
}
/* This code is contributed by Harsh kedia */

// Java program for the
// above approach
import java.util.*;
class Main{
     
// Recursive program to
// bring 'x' to the end
public static void rec(char a[],
                       int i)
{        
  // When the string is completed
  // from reverse direction end
  // of recursion
  if(i == 0)
  {
    System.out.println(a);
    return;
  }
 
  // If the character x is found
  if(a[i] == 'x')
  {
 
    // Transverse the whole string
    int j = i;
    while(a[j] != '\0' &&
          a[j + 1] != '\0')
    {
      // Swap the x so that
      // it moves to the last
      char temp = a[j];
      a[j] = a[j + 1];
      a[j + 1] = temp;
      j++;
    }
  }
 
  // call to the smaller
  // problem now
  rec(a, i - 1);
}  
 
// Driver code
public static void main(String[] args)
{
  char a[] = {'g', 'e', 'e', 'k',
              'x', 's', 'x', 'x',
              'k', 's', '\0'};
 
  // Size of a
  int n = 10;
 
  // Call to rec
  rec(a,n-1);
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program for above approach
 
# Recursive program to bring 'x'
# to the end
def rec(a, i):
      
    # When the string is completed
    # from reverse direction end
    # of recursion
    if (i == 0):
        a.pop()
        print("".join(a))
        return
     
    # If the character x is found
    if (a[i] == 'x'):
        
      # Transverse the whole string
      j = i
      while(a[j] != '\0' and
            a[j + 1] != '\0'):
          
        # Swap the x so that
        # it moves to the last
        (a[j], a[j + 1]) = (a[j + 1], a[j])
        j += 1
       
    # Call to the smaller problem now
    rec(a, i - 1)
 
# Driver code
if __name__=="__main__":
     
    a = [ 'g', 'e', 'e', 'k', 'x',
          's', 'x', 'x', 'k', 's', '\0' ]
      
    # Size of a
    n = 10
    
    # Call to rec
    rec(a, n - 1)
 
# This code is contributed by rutvik_56

// C# program for the
// above approach
using System;
class GFG
{
     
    // Recursive program to
    // bring 'x' to the end
    static void rec(char[] a, int i)
    {
       
      // When the string is completed
      // from reverse direction end
      // of recursion
      if(i == 0)
      {
        Console.WriteLine(a);
        return;
      }
      
      // If the character x is found
      if(a[i] == 'x')
      {
      
        // Transverse the whole string
        int j = i;
        while(a[j] != '\0' &&
              a[j + 1] != '\0')
        {
           
          // Swap the x so that
          // it moves to the last
          char temp = a[j];
          a[j] = a[j + 1];
          a[j + 1] = temp;
          j++;
        }
      }
      
      // call to the smaller
      // problem now
      rec(a, i - 1);
    }
   
  // Driver code    
  static void Main()
  {
      char[] a = {'g', 'e', 'e', 'k',
              'x', 's', 'x', 'x',
              'k', 's', '\0'};
  
      // Size of a
      int n = 10;
      
      // Call to rec
      rec(a,n-1);
  }
}
 
// This code is contributed by divyesh072019

<script>
    // Javascript program for the above approach
     
    // Recursive program to
    // bring 'x' to the end
    function rec(a, i)
    {
        
      // When the string is completed
      // from reverse direction end
      // of recursion
      if(i == 0)
      {
        document.write(a.join(""));
        return;
      }
       
      // If the character x is found
      if(a[i] == 'x')
      {
       
        // Transverse the whole string
        let j = i;
        while(a[j] != '\0' &&
              a[j + 1] != '\0')
        {
            
          // Swap the x so that
          // it moves to the last
          let temp = a[j];
          a[j] = a[j + 1];
          a[j + 1] = temp;
          j++;
        }
      }
       
      // call to the smaller
      // problem now
      rec(a, i - 1);
    }
     
    let a = ['g', 'e', 'e', 'k', 'x', 's', 'x', 'x', 'k', 's', '\0'];
   
    // Size of a
    let n = 10;
 
    // Call to rec
    rec(a, n - 1);
     
    // This code is contributed by decode2207.
</script>

geeksksxxx

Complejidad de tiempo: O(N), donde N es la longitud de la string dada.
Espacio Auxiliar: O(N).