logo

TechCodeview

Rotação à esquerda de uma corda

Dada uma string é e um número inteiro d a tarefa é girar para a esquerda  a string por  d  posições.

Exemplos:

Entrada : s = 'GeeksforGeeks' d = 2
Saída : 'exforGeeksGe'
Explicação : Após a primeira rotação, a string s se torna ' eeksforGeeksG' e após a segunda rotação torna-se ' exforGeeksGe' .



Entrada : s = 'qwertyu' d = 2
Saída : 'ertuqw'
Explicação : Após a primeira rotação, a string s se torna ' Werq' e após a segunda rotação torna-se ' Ertuq' .

Índice

[Abordagem ingênua] Gire para a esquerda um por um

T A ideia é armazenar o primeiro caractere em uma variável e mudança todos os restante personagens para o esquerda por uma posição e depois coloque o primeiro caractere no final da string. Este processo é repetido d vezes.

C++ 
// C++ Program to left rotate the string by d  // positions by rotating one element at a time #include    #include  using namespace std;   void rotateString(string &s int d) {  int n = s.size();  // Repeat the rotation d times  for (int i = 0; i < d; i++) {  // Left rotate the string by one position  int first = s[0];  for (int j = 0; j < n - 1; j++)   s[j] = s[j + 1];    // Place the first character at the end  s[n - 1] = first;  } } int main() {  string s = 'GeeksforGeeks';  int d = 2;  rotateString(s d);  cout << s << endl;  return 0; }
C 
// C Program to left rotate the string by d positions // by rotating one element at a time #include  #include  void rotateString(char s[] int d) {  int n = strlen(s);  // Repeat the rotation d times  for (int i = 0; i < d; i++) {  // Left rotate the string by one position  char first = s[0];  for (int j = 0; j < n - 1; j++)   s[j] = s[j + 1];    // Place the first character at the end  s[n - 1] = first;  } } int main() {  char s[] = 'GeeksforGeeks';  int d = 2;  rotateString(s d);  printf('%sn' s);  return 0; }
Java 
// Java Program to left rotate the string by d positions // by rotating one element at a time import java.util.Arrays; class GfG {  static String rotateString(String s int d) {  // Convert the string to a char array  char[] charArray = s.toCharArray();  int n = charArray.length;  // Perform the rotation d times  for (int i = 0; i < d; i++) {  // Store the first character  char first = charArray[0];  // Shift each character one position to  // the left  for (int j = 0; j < n - 1; j++)  charArray[j] = charArray[j + 1];  // Move the first character to the end  charArray[n - 1] = first;  }    return new String(charArray);  }  public static void main(String[] args) {  String s = 'GeeksforGeeks';  int d = 2;  String rotatedString = rotateString(s d);  System.out.println(rotatedString);  } }
Python 
# python Program to left rotate the string by d  # positions by rotating one element at a time def rotateString(s d): # Convert the string to a list of  # characters s = list(s) n = len(s) # Perform the rotation d times for _ in range(d): # Store the first character first = s[0] # Shift each character one  # position to the left for i in range(n - 1): s[i] = s[i + 1] # Move the first character to the end s[n - 1] = first # Convert the list back to a string return ''.join(s) s = 'GeeksforGeeks' d = 2 rotatedString = rotateString(s d) print(rotatedString)
C# 
// C# Program to left rotate the string by d positions // by rotating one element at a time using System; class GfG {  static string rotateString(string s int d) {    // Convert the string to a character array  char[] charArray = s.ToCharArray();  int n = charArray.Length;  // Perform the rotation d times  for (int i = 0; i < d; i++) {    // Store the first character  char first = charArray[0];  // Shift each character one position to   // the left  for (int j = 0; j < n - 1; j++)   charArray[j] = charArray[j + 1];  // Move the first character to the end  charArray[n - 1] = first;  }  // Convert the character array to a string  return new string(charArray);  }  static void Main() {  string s = 'GeeksforGeeks';  int d = 2;  string rotatedString = rotateString(s d);  Console.WriteLine(rotatedString);  } }
JavaScript 
// Javascript Program to left rotate the string by d positions // by rotating one element at a time function rotateString(s d) {  // Convert the string to an array  let charArray = s.split('');  let n = charArray.length;  // Perform the rotation d times  for (let i = 0; i < d; i++) {    // Store the first character  let first = charArray[0];    // Shift each character one position to the left  for (let j = 0; j < n - 1; j++)   charArray[j] = charArray[j + 1];    // Move the first character to the end  charArray[n - 1] = first;  }  // Convert the array back to a string  return charArray.join(''); } let s = 'GeeksforGeeks'; let d = 2; let rotatedString = rotateString(s d); console.log(rotatedString);

Saída 
eksforGeeksGe

Complexidade de tempo:  O(n*d) o loop externo é executado  d   tempos e execuções de loop interno n  vezes.
Espaço Auxiliar: O(1) se a string for mutável como em C++. Para cadeias imutáveis como em Java C# Python e Javascript, uma matriz de caracteres extra de tamanho n é usada para que a complexidade do espaço seja O (n).

[Melhor abordagem] Usando matriz de caracteres temporários

A ideia é usar um array de caracteres temporário de tamanho n (tamanho da string original). Se sairmos, gire a corda por d posiciona o último n-d elementos estarão no frente e o primeiro d elementos estarão no fim .

  • Copie o últimos (n – d) elementos da string original no primeiro n-d posições da matriz temporária.
  • Então copie o primeiros d elementos da string original até o final da matriz temporária.
  • Finalmente converter a matriz de caracteres temporária para a string.
C++ 
// C++ program to left rotate a string by d // position using a temporary array #include    #include  using namespace std; string rotateString(string &s int d) {  int n = s.length();  // Handle cases where d > n  d = d % n;  char temp[n];  // Copy the last (n - d) characters  // to the start of temp Array  for (int i = 0; i < n - d; i++)  temp[i] = s[d + i];  // Copy the first d characters to the end  // of temp Array  for (int i = 0; i < d; i++)  temp[n - d + i] = s[i];  // Convert temp array to the string  return string(temp n); } int main() {  string s = 'GeeksforGeeks';  int d = 2;  string rotatedString = rotateString(s d);  cout << rotatedString << endl;  return 0; }
Java 
// Java program to left rotate a string by d position // using a temporary array import java.io.*; class GfG {  static String rotateString(String s int d) {  int n = s.length();    // Handle cases where d > n  d = d % n;   char[] temp = new char[n];  // Copy the last (n - d) characters to the   // start of temp array  for (int i = 0; i < n - d; i++)   temp[i] = s.charAt(d + i);  // Copy the first d characters to the end of  // temp array  for (int i = 0; i < d; i++)   temp[n - d + i] = s.charAt(i);  // Convert the temp array back to the String   return new String(temp);  }  public static void main(String[] args) {  String s = 'GeeksforGeeks';  int d = 2;  String rotatedString = rotateString(s d);  System.out.println(rotatedString);  } }
Python 
# Python program to left rotate a string  # by d position using a temporary array def rotateString(s d): n = len(s) # Handle cases where d > n d = d % n # Create a temporary array of the # same length as s temp = [''] * n # Copy the last (n - d) characters  # to the start of temp array for i in range(n - d): temp[i] = s[d + i] # Copy the first d characters to the  #end of temp array for i in range(d): temp[n - d + i] = s[i] # Convert temp array back to the string return ''.join(temp) s = 'GeeksforGeeks' d = 2 rotatedString = rotateString(s d) print(rotatedString)
C# 
// C# program to left rotate a string by d position  // using temporary array using System; class GfG {  static string rotateString(string s int d) {  int n = s.Length;  // Handle cases where d > n  d = d % n;  char[] temp = new char[n];  // Copy the last (n - d) characters   // to the start of temp array  for (int i = 0; i < n - d; i++)   temp[i] = s[d + i];    // Copy the first d characters to the end   // of temp array  for (int i = 0; i < d; i++)   temp[n - d + i] = s[i];    // Convert temp array back to the string  return new string(temp);  }  static void Main() {  string s = 'GeeksforGeeks';  int d = 2;  string rotatedString = rotateString(s d);  Console.WriteLine(rotatedString);  } }
JavaScript 
// Javascript program to left rotate a string  // by d position using temporary array function rotateString(s d) {  let n = s.length;  // Handle cases where d > n  d = d % n;  let temp = new Array(n);  // Copy the last (n - d) characters to   // the start of temp array  for (let i = 0; i < n - d; i++)   temp[i] = s[d + i];    // Copy the first d characters   // to the end of temp array  for (let i = 0; i < d; i++)   temp[n - d + i] = s[i];    // Convert the array back to the string  return temp.join(''); } let s = 'GeeksforGeeks'; let d = 2; let rotatedString = rotateString(s d); console.log(rotatedString);

Saída 
eksforGeeksGe

Complexidade de tempo:  O(n), pois estamos visitando cada elemento apenas duas vezes.
Espaço Auxiliar:  O(n), pois estamos usando uma matriz de caracteres adicional.

[Abordagem esperada - 1] Usando algoritmo de malabarismo

A ideia por trás do algoritmo de malabarismo é que podemos girar todos os elementos em um ciclo. Cada ciclo é independente e representa um grupo de elementos que irão se deslocar entre si durante a rotação. Se o começando índice de um ciclo é eu então os próximos elementos do ciclo estarão presentes nos índices (eu + d)% n (eu + 2d)%n (eu + 3d)%n ... e assim por diante até voltarmos ao índice i. O número total de ciclos será MDC de n e d . E realizamos um rotação única à esquerda dentro de cada ciclo.

Para saber mais sobre o algoritmo Juggling, consulte este artigo - Algoritmo de malabarismo para rotação de array .

C++ 
// C++ Program to left rotate the string by d positions // using Juggling Algorithm #include    #include  #include    using namespace std; void rotateString(string &s int d) {  int n = s.size();  // Handle the case where d > size of array  d %= n;  // Calculate the number of cycles in the rotation  int cycles = __gcd(n d);  // Perform a left rotation within each cycle  for (int i = 0; i < cycles; i++) {  // Start element of current cycle  char startChar = s[i];  // Start index of current cycle  int currIdx = i nextIdx;  // Rotate elements till we reach the start of cycle  while (true) {  nextIdx = (currIdx + d) % n;  if (nextIdx == i)  break;  // Update the next index with the current element  s[currIdx] = s[nextIdx];  currIdx = nextIdx;  }  // Copy the start element of current cycle   // at the last index of the cycle  s[currIdx] = startChar;  } } int main() {  string s = 'GeeksforGeeks';  int d = 2;  rotateString(s d);  cout << s << endl;  return 0; }
C 
// C Program to left rotate the string by d positions // using Juggling Algorithm #include  #include  void rotateString(char s[] int d) {  int n = strlen(s);  // Handle the case where d > size of array  d %= n;  // Calculate the number of cycles in the  // rotation  int cycles = gcd(n d);  // Perform a left rotation within each cycle  for (int i = 0; i < cycles; i++) {  // Start element of the current cycle  char startChar = s[i];  // Start index of the current cycle  int currIdx = i nextIdx;  // Rotate elements until we return to the  // start of the cycle  while (1) {  nextIdx = (currIdx + d) % n;  if (nextIdx == i)  break;  // Update the current index with the  // element at the next index  s[currIdx] = s[nextIdx];  currIdx = nextIdx;  }  // Place the start element of the current  // cycle at the last index  s[currIdx] = startChar;  } } int gcd(int a int b) {  if (b == 0)  return a;  return gcd(b a % b); } int main() {  char s[] = 'GeeksforGeeks';  int d = 2;  rotateString(s d);  printf('%sn' s);  return 0; }
Java 
// Java Program to left rotate the string by d positions // using Juggling Algorithm import java.io.*; class GfG {  static String rotateString(String s int d) {  int n = s.length();  // Handle the case where   // d > size of the string  d %= n;  // Calculate the number of   // cycles (GCD of n and d)  int cycles = gcd(n d);  // Convert string to character array  char[] arr = s.toCharArray();  // Perform a left rotation within each cycle  for (int i = 0; i < cycles; i++) {    // Start element of current cycle  char temp = arr[i];  int j = i;  while (true) {  int k = (j + d) % n;  if (k == i) {  break;  }  // Move the element to the next index  arr[j] = arr[k];  j = k;  }    // Place the saved element in the   // last position of the cycle  arr[j] = temp;  }  // Convert the rotated character   // array back to a string  return new String(arr);  }  // function to calculate GCD of two numbers  static int gcd(int a int b) {  if (b == 0) {  return a;  }  return gcd(b a % b);  }  public static void main(String[] args) {  String s = 'GeeksforGeeks';  int d = 2;  String rotatedString = rotateString(s d);  System.out.println(rotatedString);  } }
Python 
# python Program to left rotate the string by  # d positions using Juggling Algorithm def gcd(a b): while b: a b = b a % b return a def rotateString(s d): n = len(s) # Handle the case where d > size of # the string d %= n # Calculate the number of cycles (GCD # of n and d) cycles = gcd(n d) # Convert string to a list of characters arr = list(s) # Perfrom a left rotation wihtin each cycle for i in range(cycles): # Start element of current cycle temp = arr[i] j = i while True: k = (j + d) % n if k == i: break # Move the element to the next # index arr[j] = arr[k] j = k # Place the saved element in the last # position of the cycle arr[j] = temp # Convert the list of characters back to # a string and return return ''.join(arr) s = 'GeeksforGeeks' d = 2 rotatedString = rotateString(s d) print(rotatedString)
C# 
// C# Program to left rotate the string by d positions // using Juggling Algorithm using System; class GfG {  static int Gcd(int a int b) {  while (b != 0) {  int temp = b;  b = a % b;  a = temp;  }  return a;  }  static string rotateString(string s int d) {  int n = s.Length;  // Handle the case where d > size of the string  d %= n;  // Calculate the number of cycles (GCD of n and d)  int cycles = Gcd(n d);  // Convert string to a character array  char[] arr = s.ToCharArray();  // Perform a left rotation within each cycle  for (int i = 0; i < cycles; i++) {    // Start element of the current cycle  char temp = arr[i];  int j = i;  while (true) {  int k = (j + d) % n;  if (k == i)  break;  // Move the element to the next index  arr[j] = arr[k];  j = k;  }  // Place the saved element in the last position  // of the cycle  arr[j] = temp;  }  // Convert the character array back to a string  return new string(arr);  }  static void Main() {  string s = 'GeeksforGeeks';  int d = 2;  string rotatedString = rotateString(s d);  Console.WriteLine(rotatedString);  } }
JavaScript 
// JavaScript Program to left rotate the string by d  // positions using Juggling Algorithm function gcd(a b) {  while (b !== 0) {  let temp = b;  b = a % b;  a = temp;  }  return a; } function rotateString(s d) {  let n = s.length;  // Handle the case where d > size of the string  d %= n;  // Calculate the number of cycles (GCD of n and d)  let cycles = gcd(n d);  // Convert string to a character array  let arr = s.split('');  // Perform a left rotation within each cycle  for (let i = 0; i < cycles; i++) {    // Start element of the current cycle  let temp = arr[i];  let j = i;  while (true) {  let k = (j + d) % n;  if (k === i) {  break;  }  // Move the element to the next index  arr[j] = arr[k];  j = k;  }  // Place the first element in the last position   // of the cycle  arr[j] = temp;  }  // Convert the character array back to a string   return arr.join(''); } let s = 'GeeksforGeeks'; let d = 2; let rotatedString = rotateString(s d); console.log(rotatedString);

Saída 
eksforGeeksGe

Complexidade de tempo:  Sobre)
Espaço Auxiliar: O(1) se a string for mutável como em C++. Para cadeias imutáveis como em Java C# Python e Javascript, uma matriz de caracteres extra de tamanho n é usada para que a complexidade do espaço seja O (n).

[Abordagem Esperada - 2] Usando Algoritmo de Reversão

A ideia é baseada na observação de que se deixarmos a corda girar d posiciona o último (n-d) elementos estarão na frente e o primeiro d os elementos estarão no final.

  • Reverter a substring que contém o primeiro d elementos da string.
  • Reverter a substring que contém o último (n - d) elementos da string.
  • Finalmente inverter todos os elementos da corda.
C++ 
// C++ program to left rotate a string by d position // using Reversal Algorithm #include    #include  #include    using namespace std; void rotateString(string &s int d) {  int n = s.size();  // Handle the case where d > size of array  d %= n;  // Reverse the first d elements  reverse(s.begin() s.begin() + d);  // Reverse the remaining n-d elements  reverse(s.begin() + d s.end());  // Reverse the entire string  reverse(s.begin() s.end()); } int main() {  string s = 'GeeksforGeeks';  int d = 2;  rotateString(s d);  cout << s << endl;  return 0; }
Java 
// Java program to left rotate a string by d position // using Reversal Algorithm import java.io.*; class GfG {  static String rotateString(String s int d) {  int n = s.length();  // Handle the case where d > size of string  d %= n;  // Convert string to a character array  char[] temp = s.toCharArray();  // Reverse the first d elements  reverse(temp 0 d - 1);  // Reverse the remaining n-d elements  reverse(temp d n - 1);  // Reverse the entire array  reverse(temp 0 n - 1);  // Convert the array back to a string and return  return new String(temp);  }  static void reverse(char[] temp int start int end) {  while (start < end) {  char c = temp[start];  temp[start] = temp[end];  temp[end] = c;  start++;  end--;  }  }  public static void main(String[] args) {  String s = 'GeeksforGeeks';  int d = 2;  String rotatedString = rotateString(s d);  System.out.println(rotatedString);  } }
Python 
# Python program to left rotate a string by d positons # using Reversal Algorithm def rotateString(s d): n = len(s) # Handle cases where d > n d %= n # Convert the string to a list of characters temp = list(s) # Reverse the first d elements reverse(temp 0 d - 1) # Reverse the remaining n - d elements reverse(temp d n - 1) # Reverse the entire array reverse(temp 0 n - 1) # Convert the list back to a string and return return ''.join(temp) def reverse(temp start end): while start < end: temp[start] temp[end] = temp[end] temp[start] start += 1 end -= 1 s = 'GeeksforGeeks' d = 2 rotatedString = rotateString(s d) print(rotatedString)
C# 
// C++ program to left rotate a string by d positions // using Reversal Algorithm using System; class GfG {  static string RotateString(string s int d) {  int n = s.Length;  // Handle cases where d > n  d %= n;  // Convert the string to a character array  char[] temp = s.ToCharArray();  // Reverse the first d elements  Reverse(temp 0 d - 1);  // Reverse the remaining n - d elements  Reverse(temp d n - 1);  // Reverse the entire array  Reverse(temp 0 n - 1);  // Convert the character array back to a string  return new string(temp);  }  static void Reverse(char[] temp int start int end) {  while (start < end) {  char c = temp[start];  temp[start] = temp[end];  temp[end] = c;  start++;  end--;  }  }  static void Main() {  string s = 'GeeksforGeeks';  int d = 2;  string rotatedString = RotateString(s d);  Console.WriteLine(rotatedString);  } }
JavaScript 
// C++ program to left rotate a string by d position // using Reversal Algorithm function rotateString(s d) {  const n = s.length;  // Handle cases where d > n  d %= n;  // Convert the string to a character array  let temp = s.split('');  // Reverse the first d elements  reverse(temp 0 d - 1);  // Reverse the remaining n - d elements  reverse(temp d n - 1);  // Reverse the entire array  reverse(temp 0 n - 1);  // Convert the array back to a string  return temp.join(''); }   function reverse(temp start end) {  while (start < end) {    // Swap elements  [temp[start] temp[end]]   = [temp[end] temp[start]];  start++;  end--;  } } let s = 'GeeksforGeeks'; let d = 2; let rotatedString = rotateString(s d); console.log(rotatedString);

Saída 
eksforGeeksGe

Complexidade de tempo: O(n) onde n é o tamanho da string fornecida.
Espaço Auxiliar: O(1) se a string for mutável como em C++. Para cadeias imutáveis como em Java C# python e Javascript, uma matriz de caracteres extra de tamanho n é usada para que a complexidade do espaço seja O (n).

Criar questionário