Minimize operations to restore original string by permutation
Given a string S and permutation P, both of length N. In one operation you can change the position of each and every character of the string from S[i] to S[P[i]]. Determine the minimum number of operations to restore the original string.
Examples:
Input: S = “ababa”, P = [3, 4, 5, 2, 1]
Output: 1
Explanation: After first operation on S, we will get S’ = “ababa”. Since S’ = S, so min number of operations = 1.Input: S=”ababa”, P = [2, 1, 4, 5, 3]
Output: 6
Explanation:
- After first operation on S, we will get S’ = “babaa”.
- After second operation on S, we will get S” = “abaab”.
- After third operation on S, we will get S”’ = “baaba”.
- After fourth operation on S, we will get S”” = “abbaa”.
- After fifth operation on S, we will get S””’ = “baaab”.
- After sixth operation on S, we will get S””” = “ababa”. Since S””” = S, so min number of operations= 6.
Approach: To solve the problem, follow the below idea:
If we observe carefully, then each character of the original string S will reach back to its original position after some operations. So, if we keep on applying the operation continuously then each of the character will move in a cycle across the string S. So, the approach is to identify cycles in a permutation, represented by the vector P, and compute the lengths of these cycles, and calculates their Least Common Multiple (LCM) to determine the final result. The process is based on traversing the permutation indices and forming cycles, leveraging the cyclic property of the permutation.
Intuition:
- Each cycle is formed by following the permutation until a previously visited index is reached.
- The length of a cycle is found by searching for the starting position of the substring in the doubled string.
- The LCM is used to accumulate the lengths of cycles for different starting positions, ensuring that the final result represents the shortest repeating cycle for the entire permutation.
It finds the length of the shortest repeating cycle in a given permutation of a string by leveraging the LCM property of cycle lengths.
Step-by-step algorithm:
- The main loop iterates through the indices i from 1 to N.
- If the index i is not visited (!used[i]), it starts a cycle.
- Inside the cycle, it creates a string t by traversing the permutation until it reaches a previously visited index.
- For each cycle, it calculates the length of the cycle (cyc) by finding the position of the first occurrence of the substring t in the concatenated string t + t starting from position 1.
- The answer (ans) is updated by taking the least common multiple (LCM) of the current answer and the length of the cycle (cyc).
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; using ll = long long ; // Function to calculate the least common multiple (LCM) long long lcm( long long a, long long b) { return (a * b) / __gcd(a, b); } int main() { // Driver code string S = "ababa" ; long long N = 5; vector<ll> P = {2, 1, 4, 5, 3 }; // 0-based indexing for ( int i = 0; i < N; i++) { P[i] -= 1; } // Array to mark visited indices during iteration vector<ll> used(N + 1); // Initialize the answer variable to 1 ll ans = 1; // Iterate through each index in the permutation for ( int i = 1; i <= N; i++) // If the index is not visited,start a new cycle if (!used[i]) { string t; // Generate a cycle by following the permutation // until a previously visited index is // encountered for (ll j = i; !used[j]; j = P[j]) { // Mark the index as visited used[j] = 1; // Build the cycle substring t += S[j - 1]; } // Calculate the length of the cycle by finding // the starting position of the substring in the // doubled string ll cyc = (t + t).find(t, 1); // Update the answer by taking the LCM with the // current cycle length ans = lcm(ans, cyc); } cout << ans; } |
Java
// Java Implementation import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) { // Example usage String S = "ababa" ; List<Integer> P = new ArrayList<>(); P.add( 2 ); P.add( 1 ); P.add( 4 ); P.add( 5 ); P.add( 3 ); System.out.println(minOperations(S, P)); // Output: 6 } // Function to calculate the minimum number of operations required // to form a cycle using the given permutation public static int minOperations(String S, List<Integer> P) { int N = S.length(); List<Boolean> visited = new ArrayList<>(N + 1 ); // Initialize the visited array with false for ( int i = 0 ; i <= N; i++) { visited.add( false ); } int result = 1 ; // Initialize the result variable to 1 // Iterate through each index in the permutation for ( int i = 1 ; i <= N; i++) { // If the index is not visited, start a new cycle if (!visited.get(i)) { int cycleLength = 0 ; int j = i; // Generate a cycle by following the permutation // until a previously visited index is encountered while (!visited.get(j)) { visited.set(j, true ); j = P.get(j - 1 ); cycleLength++; } // Update the result by taking the LCM with the // current cycle length result = lcm(result, cycleLength); } } return result; } // Function to calculate the greatest common divisor (GCD) public static int gcd( int a, int b) { while (b != 0 ) { int temp = b; b = a % b; a = temp; } return a; } // Function to calculate the least common multiple (LCM) public static int lcm( int a, int b) { return (a * b) / gcd(a, b); } } //This code is contributed by Tapesh(tapeshdu420) |
C#
using System; using System.Collections.Generic; class Program { static void Main() { // Example usage string S = "ababa" ; List< int > P = new List< int > { 2, 1, 4, 5, 3 }; Console.WriteLine(MinOperations(S, P)); // Output: 6 } static int MinOperations( string S, List< int > P) { int N = S.Length; List< bool > visited = new List< bool >( new bool [N + 1]); int result = 1; for ( int i = 1; i <= N; i++) { if (!visited[i]) { int cycleLength = 0; int j = i; while (!visited[j]) { visited[j] = true ; j = P[j - 1]; cycleLength++; } result = LCM(result, cycleLength); } } return result; } static int GCD( int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } static int LCM( int a, int b) { return (a * b) / GCD(a, b); } } |
Javascript
// Function to calculate the greatest common divisor (GCD) function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); } // Function to calculate the least common multiple (LCM) function lcm(a, b) { return (a * b) / gcd(a, b); } // Driver code const S = "ababa" ; const N = 5; const P = [2, 1, 4, 5, 3].map(x => x - 1); // Convert to 0-based indexing // Array to mark visited indices during iteration const used = new Array(N + 1).fill(0); // Initialize the answer variable to 1 let ans = 1; // Iterate through each index in the permutation for (let i = 0; i < N; i++) { // If the index is not visited, start a new cycle if (!used[i]) { let t = "" ; // Generate a cycle by following the permutation // until a previously visited index is encountered for (let j = i; !used[j]; j = P[j]) { // Mark the index as visited used[j] = 1; // Build the cycle substring t += S[j]; } // Calculate the length of the cycle by finding // the starting position of the substring in the // doubled string const cyc = t.length; // Update the answer by taking the LCM with the // current cycle length ans = lcm(ans, cyc); } } console.log(ans); //This code is contributed by Aman. |
Python3
# Python Implementation def min_operations(S, P): N = len (S) visited = [ False ] * (N + 1 ) result = 1 # Initialize the result variable to 1 # Iterate through each index in the permutation for i in range ( 1 , N + 1 ): # If the index is not visited, start a new cycle if not visited[i]: cycle_length = 0 j = i # Generate a cycle by following the permutation # until a previously visited index is encountered while not visited[j]: visited[j] = True j = P[j - 1 ] cycle_length + = 1 # Update the result by taking the LCM with the # current cycle length result = lcm(result, cycle_length) return result # Function to calculate the greatest common divisor (GCD) def gcd(a, b): while b ! = 0 : temp = b b = a % b a = temp return a # Function to calculate the least common multiple (LCM) def lcm(a, b): return (a * b) / / gcd(a, b) # Example usage if __name__ = = "__main__" : # Example usage S = "ababa" P = [ 2 , 1 , 4 , 5 , 3 ] print (min_operations(S, P)) # Output: 6 #this code is contributed by Adarsh |
6
Time Complexity: O(N), where N is the length of the permutation.
Auxiliary Space: O(N).
Contact Us