Given two strings A and B which are permutations of each other. The task is to find the minimum number of rotations required to delete both strings completely. We can delete the first characters of both strings if they are the same. Otherwise, the string is rotated one position to left.
Examples:
Input: A = “abcd”, B = “bcda”
Output: 1
Explanation: rotate A, only one left rotation is required to make both strings equalInput: A=”geek” B=”geek”
Output : 0
Explanation: Both strings are equal hence the number of operations is 0.
Approach:
The basic idea is to check if A is and B are rotations of each other or not.
- Initialize rotations = 0 (Count of rotations)
- Check whether the first character of both strings are same or not.
- If not, then apply left rotation on string A and increment rotations.
- If the first characters are the same, delete the first character of both strings.
- Check whether both strings are empty.
- If yes then break the loop.
- Else go to step 2 and repeat it from the next index.
Below is the Implementation of the above approach.
C++14
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to perform left rotationstring leftrotate(string& s, int d){ reverse(s.begin(), s.begin() + d); reverse(s.begin() + d, s.end()); reverse(s.begin(), s.end()); return s;}// Function to find the minimum number of rotationsint MinimumRotations(string A, string B){ int rotations = 0; int len = A.length(); int B_index = 0; for (int i = 0; i < len; i++) { // Character removal if first character is same if (A[0] == B[B_index]) { A.erase(A.begin() + 0); B_index++; } // Left rotation if its not same if (A[0] != B[B_index]) { A = leftrotate(A, 1); rotations++; i = 0; } } // Return final rotations required return rotations;}// Driver codeint main(){ string A = "geek"; string B = "geek"; cout << MinimumRotations(A, B) << endl; string A2 = "abcd"; string B2 = "bcda"; cout << MinimumRotations(A2, B2) << endl; string A3 = "agef"; string B3 = "afge"; cout << MinimumRotations(A3, B3) << endl; return 0;} |
Java
// Java code to implement the approachpublic class Main { // Driver code public static void main(String[] args) { String A = "geek"; String B = "geek"; System.out.println(MinimumRotations(A, B)); String A2 = "abcd"; String B2 = "bcda"; System.out.println(MinimumRotations(A2, B2)); String A3 = "agef"; String B3 = "afge"; System.out.println(MinimumRotations(A3, B3)); } // Function to find the minimum number of rotations public static int MinimumRotations(String A, String B) { int rotations = 0; int len = A.length(); int B_index = 0; for (int i = 0; i < len; i++) { // Character removal if first character is same if (A.charAt(0) == B.charAt(B_index)) { A = A.substring(1); B_index++; } // Left rotation if its not same else if (A.charAt(0) != B.charAt(B_index)) { A = leftrotate(A, 1); rotations++; i = 0; } } // Return final rotations required return rotations; } // Function to perform left rotation public static String leftrotate(String s, int d) { String ans = s.substring(d) + s.substring(0, d); return ans; }}// This code is contributed by Tapesh(tapeshdua420) |
Python3
# Python code to implement the approach# Function to perform left rotationdef leftrotate(s, d): return s[d:] + s[:d]# Function to find the minimum number of rotationsdef MinimumRotations(A, B): rotations = 0 len_A = len(A) B_index = 0 for i in range(len_A): # Character removal if first character is same if A[0] == B[B_index]: A = A[1:] B_index += 1 # Left rotation if its not same elif A[0] != B[B_index]: A = leftrotate(A, 1) rotations += 1 i = 0 # Return final rotations required return rotations# Driver codeif __name__ == '__main__': A = "geek" B = "geek" print(MinimumRotations(A, B)) A2 = "abcd" B2 = "bcda" print(MinimumRotations(A2, B2)) A3 = "agef" B3 = "afge" print(MinimumRotations(A3, B3))# This code is contributed by Tapesh(tapeshdua420) |
C#
using System;class Program { // Driver Code static void Main(string[] args) { string A = "geek"; string B = "geek"; Console.WriteLine(MinimumRotations(A, B)); string A2 = "abcd"; string B2 = "bcda"; Console.WriteLine(MinimumRotations(A2, B2)); string A3 = "agef"; string B3 = "afge"; Console.WriteLine(MinimumRotations(A3, B3)); } // Function to find the minimum number of rotations public static int MinimumRotations(string A, string B) { int rotations = 0; int len = A.Length; int B_index = 0; for (int i = 0; i < len; i++) { // Character removal if first character is same if (A[0] == B[B_index]) { A = A.Substring(1); B_index++; } // Left rotation if its not same else if (A[0] != B[B_index]) { A = leftrotate(A, 1); rotations++; i = 0; } } // Return final rotations required return rotations; } // Function to perform left rotation public static string leftrotate(string s, int d) { string ans = s.Substring(d) + s.Substring(0, d); return ans; }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// JavaScript code to implement the approach // Function to perform left rotation function leftrotate(s, d) { return s.substr(d) + s.substr(0, d); } // Function to find the minimum number of rotations function MinimumRotations(A, B) { rotations = 0; len_A = A.length; B_index = 0; for (i = 0; i < len_A; i++) { // Character removal if first character is same if (A[0] == B[B_index]) { A = A.substr(1); B_index += 1; } // Left rotation if its not same else if (A[0] != B[B_index]) { A = leftrotate(A, 1); rotations += 1; i = 0; } } // Return final rotations required return rotations; } // Driver code A = "geek"; B = "geek"; console.log(MinimumRotations(A, B)); A2 = "abcd"; B2 = "bcda"; console.log(MinimumRotations(A2, B2)); A3 = "agef"; B3 = "afge"; console.log(MinimumRotations(A3, B3)); // This code is contributed by Tapesh(tapeshdua420) |
Output
0 1 2
Time Complexity : O(N2)
Auxiliary Space : O(1)
Approach using Queue:
We can solve this problem using queue for clockwise rotation. We will append characters of string A in queue and iterate over string B. And apply left rotation on queue if required. Else remove the first character from B and pop the queue front from the queue.
- Initialize a variable (say rotations) to store the number of rotations required.
- Create a char queue to store the characters.
- Append all characters of string A in the queue.
- Start iteration over string B and check whether the first character of both strings is the same or not.
- If they are the same then delete the string.
- Otherwise, rotation is required.
- Calculate the rotations:
- Create a variable (say times) to count the number of clockwise rotations.
- Start a while loop and check if the first elements are not equal. If so, increment times variable and push the frontmost value in the queue and pop() the queue.
- Return the times variable.
- Return the rotations variable as the result.
Below is the Implementation of the above approach.
C++14
/*C++ program to determine minimum number of rotations required to delete both strings*/#include <bits/stdc++.h>using namespace std;// Clockwise rotation if characters are not sameint ClockwiseRotation(queue<char>& q, char t){ // Initialize times to count number of clockwise rotations done int times = 0; while (q.front() != t) { times++; q.push(q.front()); q.pop(); } return times;}int MinimumRotations(string A, string B){ // Initialize rotations for storing the total count int rotations = 0; queue<char> q; // Appending all the characters of A in queue for (int i = 0; i < A.size(); i++) { q.push(A[i]); } // Iterating on string B for (int i = 0; i < B.size(); i++) { // If first character is not same hence rotation is required if (B[i] != q.front()) { rotations += ClockwiseRotation(q, B[i]); } q.pop(); } // Return final answer return rotations;}// Driver codeint main(){ string A = "geek"; string B = "geek"; cout << MinimumRotations(A, B) << endl; string A2 = "abcd"; string B2 = "bcda"; cout << MinimumRotations(A2, B2) << endl; string A3 = "agef"; string B3 = "afge"; cout << MinimumRotations(A3, B3) << endl; return 0;} |
Java
// java implementationimport java.io.*;import java.util.LinkedList;import java.util.Queue;class GFG{ // Clockwise rotation if characters are not same public static int ClockwiseRotation(Queue<Character> q, char t) { // Initialize times to count number of clockwise // rotations done int times = 0; while (q.peek() != t) { times++; q.add(q.peek()); q.remove(); } return times; } public static int MinimumRotations(String A, String B) { // Initialize rotations for storing the total count int rotations = 0; Queue<Character> q = new LinkedList<Character>(); // Appending all the characters of A in queue for (int i = 0; i < A.length(); i++) { q.add(A.charAt(i)); } // Iterating on string B for (int i = 0; i < B.length(); i++) { // If first character is not same hence rotation // is required if (B.charAt(i) != q.peek()) { rotations += ClockwiseRotation(q, B.charAt(i)); } q.remove(); } // Return final answer return rotations; } public static void main(String[] args) { String A = "geek"; String B = "geek"; System.out.println( MinimumRotations(A, B)); String A2 = "abcd"; String B2 = "bcda"; System.out.println( MinimumRotations(A2, B2)); String A3 = "agef"; String B3 = "afge"; System.out.println( MinimumRotations(A3, B3)); }}// This code is contributed by ksam24000 |
Python3
# Python program to determine minimum number# of rotations required to delete both strings# Clockwise rotation if characters are not samedef ClockwiseRotation(q, t): # Initialize times to count number of clockwise rotations done times = 0 while (q[0] != t): times += 1 q.append(q[0]) q.pop(0) return times# Function to find minimum number of rotationsdef MinimumRotations(A, B): # Initialize rotations for storing the total count rotations = 0 q = [] # Appending all the characters of A in queue for i in range(len(A)): q.append(A[i]) # Iterating on string B for i in range(len(B)): # If first character is not same hence rotation is required if (B[i] != q[0]): rotations += ClockwiseRotation(q, B[i]) q.pop(0) # Return final answer return rotations# Driver codeA = "geek"B = "geek"print(MinimumRotations(A, B))A2 = "abcd"B2 = "bcda"print(MinimumRotations(A2, B2))A3 = "agef"B3 = "afge"print(MinimumRotations(A3, B3))# This code is contributed by Tapesh(tapeshdua420) |
C#
// c# implementationusing System;using System.Collections.Generic;class Program { // Clockwise rotation if characters are not same public static int ClockwiseRotation(Queue<char> q, char t) { // Initialize times to count number of clockwise // rotations done int times = 0; while (q.Peek() != t) { times++; q.Enqueue(q.Peek()); q.Dequeue(); } return times; } public static int MinimumRotations(string A, string B) { // Initialize rotations for storing the total count int rotations = 0; Queue<char> q = new Queue<char>(); // Appending all the characters of A in queue for (int i = 0; i < A.Length; i++) { q.Enqueue(A[i]); } // Iterating on string B for (int i = 0; i < B.Length; i++) { // If first character is not same hence rotation // is required if (B[i] != q.Peek()) { rotations += ClockwiseRotation(q, B[i]); } q.Dequeue(); } // Return final answer return rotations; } // Driver Code public static void Main(string[] args) { string A = "geek"; string B = "geek"; Console.WriteLine(MinimumRotations(A, B)); string A2 = "abcd"; string B2 = "bcda"; Console.WriteLine(MinimumRotations(A2, B2)); string A3 = "agef"; string B3 = "afge"; Console.WriteLine(MinimumRotations(A3, B3)); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// JavaScript program to determine minimum number // of rotations required to delete both strings // Clockwise rotation if characters are not same function ClockwiseRotation(q, t) { // Initialize times to count number of clockwise rotations done var times = 0 while (q[0] != t) { times += 1 q.push(q[0]) q.shift() } return times }// Function to find minimum number of rotations function MinimumRotations(A, B) { // Initialize rotations for storing the total count var rotations = 0 var q = [] // Appending all the characters of A in queue for (var i = 0; i < A.length; i++) { q.push(A[i]) } // Iterating on string B for (var i = 0; i < B.length; i++) { // If first character is not same hence rotation is required if (B[i] != q[0]) { rotations += ClockwiseRotation(q, B[i]) } q.shift() } // Return final answer return rotations }// Driver code var A = "geek"var B = "geek"console.log(MinimumRotations(A, B)) var A2 = "abcd"var B2 = "bcda"console.log(MinimumRotations(A2, B2)) var A3 = "agef"var B3 = "afge"console.log(MinimumRotations(A3, B3)) // This code is contributed by Tapesh(tapeshdua420) |
Output
0 1 2
Time Complexity: O(N2)
Auxiliary Space: O(N)
Related Articles:
- Introduction to Queue – Data Structures and Algorithms Tutorials
- Introduction to Strings – Data Structures and Algorithms Tutorials
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
